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 long
using 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 long
using 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 long
using 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;
}