11.6日志

1.Problem - D - Codeforces

首先很显然的是我们肯定要一列一列的找并且我们发现当小偷跟我们一开始处于奇偶不同的x格子的时候我们会完美错开同时也发现小偷每次移动x必然会移动也就是说小偷每次的x每次都会改变奇偶性因此我们让警察从1 1 1 2一直扫到最左边这时候能抓到所有开始位置在奇数格子的小偷回去的时候我们在2000 1 2000 2停留一次改变自己和小偷的相对奇偶性再向左扫一次就一定能抓到小偷

#define yyy cout<<"Yes"<<"\n" 
#define nnn cout<<"No"<<"\n" 
#define x first 
#define y second
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<ll , ll> pii;
typedef pair<string , string> pss;
const int N = 2e5 + 10,inf = 0x3f3f3f3f,mod = 19930726;int main()
{std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cout<<2000<<"\n";for(int i = 1 ; i <= 1000 ; i++){cout<<i<<" "<<1<<" "<<i<<" "<<2<<"\n";}    for(int i = 1000 ; i >= 1 ; i--){cout<<i<<" "<<1<<" "<<i<<" "<<2<<"\n";}
}

2.Problem - C - Codeforces

这题我们侧重点应该在于考虑每条边被使用的频率,在求G的时候我们应该要让每条边被使用的频率尽可能的少,那么就是对于以i为根的子树的时候若其大小为偶数就说明子树中的点可以与子树中的其他点配对消化若是奇数则说明有一个点需要与子树外的点匹配,那么我们肯定选最外层的也就是子树的根i,它连向外界的边肯定会被使用因此加上,在我们求B的时候我们希望每条边被尽可能地使用那么就是说明以i为根的子树中的点尽量跟子树外的点匹配那么我们就需要考虑一条边最多会被使用多少次,i连向j的边w会被使用的次数就是min(siz[j] , 2 * k - siz[j])

#define yyy cout<<"Yes"<<"\n" 
#define nnn cout<<"No"<<"\n" 
#define x first 
#define y second
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<ll , ll> pii;
typedef pair<string , string> pss;
const int N = 2e5 + 10,inf = 0x3f3f3f3f,mod = 19930726;vector <pii> g[N];
ll k;
ll ans,siz[N];void init()
{for(int i = 1 ; i <= 2 * k ; i++){g[i].clear();siz[i] = 0;}
}void dfs1(int u,int fa)
{siz[u] = 1;for(int i = 0 ; i < g[u].size() ; i++){int j = g[u][i].x,d = g[u][i].y;if(j == fa){continue;}dfs1(j , u);siz[u] += siz[j];if(siz[j] % 2){ans += d;}}
}void dfs2(int u,int fa)
{for(int i = 0 ; i < g[u].size() ; i++){int j = g[u][i].x,d = g[u][i].y;if(j == fa){continue;}dfs2(j , u);ans += d * min(siz[j] , 2 * k - siz[j]);}
}void work()
{cin>>k;init();for(int i = 1 ; i < 2 * k ; i++){ll u,v,z;cin>>u>>v>>z;g[u].push_back({v , z});g[v].push_back({u , z});}ans = 0;dfs1(1 , -1);cout<<ans<<" ";ans = 0;dfs2(1 , -1);cout<<ans<<"\n";
}int main()
{std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);int t;cin>>t;while(t--){work();}
}

3.B-小H学数学_牛客练习赛131

我们的状态表示为dp[i][j]即j个人凑i的方案数,为了防止x越界因此我们将x += 1000，也就是将我们凑得数整体加上1000,最内层循环就是枚举1 - 10的正负数以及1-5双重循环的组合进行转移,有一点需要注意的是内外层循环不能颠倒必须先枚举人作为最外层循环再枚举数字,因为若是先枚举数字的话那么我们之后的转移都是不准确的,例如对于i明明可以通过一个人就可以从i + 10转移但是因为我们还没有枚举到i + 10所以此时的i + 10是空的,这个时候就会产生遗漏

#define yyy cout<<"Yes"<<"\n" 
#define nnn cout<<"No"<<"\n" 
#define x first 
#define y second
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<ll , ll> pii;
typedef pair<string , string> pss;
const int N = 5e3 + 10,inf = 0x3f3f3f3f,mod = 1e9 + 7;ll dp[N][200];
int x,y;void add(int i,int j,int k)
{if(i + k >= 0 && i + k <= 2000){dp[i][j] = (dp[i][j] + dp[i + k][j - 1]) % mod;}
}int main()
{std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);cin>>x>>y;y++,x += 1000;dp[1000][0] = 1;for(int i = 1 ; i <= y ; i++){for(int j = 0 ; j <= 2000 ; j++){for(int op = 1 ; op <= 10 ; op++){add(j , i , op),add(j , i , -op);}for(int op1 = 1 ; op1 <= 5 ; op1++){for(int op2 = 1 ; op2 <= 5 ; op2++){add(j , i , op1 + op2),add(j , i , -op1 + op2);add(j , i , op1 - op2),add(j , i , -op1 - op2);}}}}cout<<dp[x][y];     
}