A
link
判断\(A\)，\(B\)之间可不可以放一个数，如果可以就是\(3\)个，不行就是\(2\)个（左右），但是如果\(A\)，\(B\)相等就只有一个。
点击查看代码
#include<bits/stdc++.h>using namespace std;signed main(){int a,b;cin >> a >> b;int x = b-a;if(x != 0){if(x%2 == 0) cout << 3;else cout << 2;}else cout << 1;return 0;}
B
link
存一下左右手在哪，模拟即可。
点击查看代码
#include<bits/stdc++.h>using namespace std;int n;
int a[105];
char s[105];signed main(){cin >> n;for(int i = 1;i <= n;++ i)cin >> a[i] >> s[i];int l = -1,r = -1,ans = 0;for(int i = 1;i <= n;++ i){if(s[i] == 'L'){if(l == -1) l = a[i];ans += abs(a[i]-l);l = a[i];}else{if(r == -1) r = a[i];ans += abs(a[i]-r);r = a[i];}}cout << ans;return 0;}
C
link
就是找等差数列。
找差分数组，如果差分数组这一段连续的最多\(k\)个数相等，那么这一段就有最多\(k+1\)个数是等差（试一下），那么就一共有\(C_{k+1}^2\)个等差数列（选两个端点）。一个数的单独计算。
点击查看代码
#include<bits/stdc++.h>#define int long longusing namespace std;int n;
int a[200005];
int ans;
int cf[200005];int c(int x){return x*(x-1)/2;
}signed main(){cin >> n;for(int i = 1;i <= n;++ i){cin >> a[i];cf[i] = a[i]-a[i-1];}ans = n;cf[n+1] = cf[n]+1;int zer = 0,cc = cf[1];for(int i = 2;i <= n+1;++ i){if(cf[i] != cc){zer++;ans += c(zer);zer = 1;cc = cf[i];}else zer++;}cout << ans;return 0;}
D
link
\(DP\)。设计\(dp\)数组\(f_{i,j,k}\)（详细见代码），考虑转移，如果这个不选，那么就是前一个的奇偶性，否则和前一个奇偶性相反，当然转移是前一个选与不选都行。最后答案是\(n\)选与不选，奇或偶的最大值。
点击查看代码
#include<bits/stdc++.h>#define int long longusing namespace std;int n;
int a[200005];
int f[200005][2][2];
//f[i][j][k]表示考虑到第i个怪物，第i个怪物放走/打败(0/1)
//当前是第奇/偶(1/0)个的最大经验值。int ff(int x,int z){return max(f[x][1][z],f[x][0][z]);
} signed main(){cin >> n;for(int i = 1;i <= n;++ i)cin >> a[i];f[0][0][1] = f[0][1][1] = -0x3f3f3f3f;for(int i = 1;i <= n;++ i){//放走f[i][0][0] = ff(i-1,0);f[i][0][1] = ff(i-1,1);//打败f[i][1][0] = ff(i-1,1)+2*a[i];f[i][1][1] = ff(i-1,0)+a[i];}cout << max(ff(n,1),ff(n,0));return 0;}
E
link
首先看到\(k\)很小，可以搜索走这些边的顺序（别忘了双向），那么又发现\(n\)很小，可以做一个全源最短路，这样搜索的时候就可以随意找两个点之间的距离了，如先走\(u_1\) ~ \(v_1\)，再走\(u_2\) ~ \(v_2\)，那么就需要\(v_1\)到\(u_2\)的最短路。结束。
点击查看代码
#include<bits/stdc++.h>#define int long longusing namespace std;int n,m;
int bk;
int b[15];
struct nd{int u,v,w;
}ed[200005];
int f[405][405];
int g[405][405];
int ans;
int da;
bool vs[15];void dfs(int x,int q){if(x > bk){da = min(da,ans+f[q][n]);return;}for(int i = 1;i <= bk;++ i){if(vs[i]) continue;int u = ed[b[i]].u,v = ed[b[i]].v,w = ed[b[i]].w;vs[i] = 1;ans += f[q][u]+w;dfs(x+1,v);ans -= f[q][u]+w;ans += f[q][v]+w;dfs(x+1,u);ans -= f[q][v]+w;vs[i] = 0;}
}void qwq(){cin >> bk;for(int i = 1;i <= bk;++ i)cin >> b[i];da = 1e18;ans = 0;dfs(1,1);cout << da << endl;
}signed main(){cin >> n >> m;for(int i = 1;i <= n;++ i)for(int j = 1;j <= n;++ j)g[i][j] = f[i][j] = 1e18;for(int i = 1;i <= n;++ i) f[i][i] = 0;for(int i = 1;i <= m;++ i){int u,v,w;cin >> u >> v >> w;ed[i].u = u;ed[i].v = v;ed[i].w = w;g[u][v] = min(g[u][v],w);g[v][u] = g[u][v];f[u][v] = min(f[u][v],w);f[v][u] = f[u][v];}for(int k = 1;k <= n;++ k){for(int i = 1;i <= n;++ i){for(int j = 1;j <= n;++ j){f[i][j] = min(f[i][j],f[i][k]+f[k][j]);}}}/*for(int i = 1;i <= n;++ i){for(int j = 1;j <= n;++ j){cout << f[i][j] << " ";}cout << endl;}*/int q;cin >> q;while(q--) qwq();return 0;}
