ABC264
VP
| A | B | C | D | E | F |
|---|---|---|---|---|---|
| 50:05 | 3:36 | 19:03 | 29:07 | 49:13 | 97:20 |
| +1 |
rk:\(471st\)
perf:\(\color{Blue}{1843}\)
A
subser(x,y)，输出 string 类型的 \(x\) 位开始的 \(y\) 个字符。
int l,r;cin>>l>>r;
cout<<((string)"atcoder").substr(l-1,r-l+1)<< "\n";
B
与中心方块的切比雪夫距离奇偶性可判断其颜色。
int x,y;cin>>x>>y;
cout<<((max(abs(x-8),abs(y-8))&1)?"black":"white");
C
反正 \(x,y \le 10\)，也没啥好讲的。
正常做法不如爆搜。
#define L(i,j,k) for(int (i)=(j);i<=(k);(i)++)
#define pb push_back
#define vi vector<int>
int k1,k2,c1,c2;
int a[20][20],b[20][20];
void work(){
cin>>k1>>c1;
L(i,1,k1) L(j,1,c1) cin>>a[i][j];
cin>>k2>>c2;
L(i,1,k2) L(j,1,c2) cin>>b[i][j];
L(i,0,((1<<k1)-1)) L(j,0,((1<<c1)-1)){
vi x,y;L(k,1,k1) if(!(i&(1<<(k-1)))) x.pb(k);
L(k,1,c1) if(!(j&(1<<(k-1)))) y.pb(k);
if(si(x)^k2||si(y)^c2) continue;
bool flag=1;
L(k,1,k2) L(l,1,c2)
if(a[x[k-1]][y[l-1]]^b[k][l]){flag=0;break;}
if(flag) return cout<<"Yes",void();
}cout<<"No";
}
D
记录每个字母目标位置，跑冒泡排序即可。
string k="atcoder";
void work(){
string s;cin>>s;
map<char,int>mp;int cnt=0;
L(i,0,6) mp[k[i]]=i;
L(i,0,6) L(j,1,6-i)
if(mp[s[j-1]]>mp[s[j]])
swap(s[j-1],s[j]),cnt++;
cout<<cnt;
}
E
并查集套路题，离线存下所有询问，倒着加边即可。
int u[N],v[N],d[N];
int si[N],f[N],t[N];
int ans,n,m,x,q;
map<int,bool>mp;
stack<int>st;
int cz(int x){return x==f[x]?x:f[x]=cz(f[x]);}
void hb(int x,int y){
x=cz(x),y=cz(y);
if(f[x]^f[y]){
if(t[x]^t[y]){
ans+=t[x]?si[y]:si[x];
t[y]=t[x]=1;
}si[y]+=si[x];f[x]=y;
}
}void work(){
cin>>n>>m>>x;L(i,1,n+m) f[i]=i;
L(i,1,n) si[i]=1;L(i,n+1,m+n) t[i]=1;
L(i,1,x) cin>>u[i]>>v[i];
cin>>q;L(i,1,q) cin>>d[i],mp[d[i]]=1;
L(i,1,x) if(!mp[i]) hb(u[i],v[i]);
R(i,q,1) st.push(ans),hb(u[d[i]],v[d[i]]);
while(!st.empty())
cout<<st.top()<<'\n',st.pop();
}
F
DP，设 \(f_{i,j,k,l},i \in \left[ 1,n \right],j \in \left[ 1,m \right]，k \in \left[ 0,1 \right]，l \in \left[ 0,1 \right]\) 表示在位置 \((i,j)\)，且 \(i\) 行翻转状况为 \(k\)，\(j\) 列翻转状况为 \(l\) 时的最小花费。
因为无论翻转顺序如何，都不会对结果有影响，所以不难得到每行和每列最多被翻转一次。
对于 \(f_{i,j,x,y}\) 的转移，就分别枚举 \(f_{i+1,j,nx,ny}\) 的值，设原本状态为 \(a_{i,j}\)，则如果两个状态之间要发生转移，首先要满足 \(a_{i,j} \operatorname{xor} x \operatorname{xor} y = a_{i+1,j} \operatorname{xor} nx \operatorname{xor} ny\) (另一种转移同理)
而且如果转移的是 \(i+1\) 的状态，则当前列的翻转情况必须相同，否则无法转移。
所以状态转移方程式写成代码就是：
#define L(i,j,k) for(int (i)=(j);(i)<=(k);(i)++)
L(i,1,n) L(j,1,m) L(x,0,1) L(y,0,1) L(nx,0,1) L(ny,0,1){
if(i+1<=n&&(a[i][j]^x^y==a[i+1][j]^nx^ny)&&y==ny)
f[i+1][j][nx][ny]=min(f[i+1][j][nx][ny],f[i][j][x][y]+(nx?r[i+1]:0));
if(j+1<=m&&(a[i][j]^x^y==a[i][j+1]^nx^ny)&&x==nx)
f[i][j+1][nx][ny]=min(f[i][j+1][nx][ny],f[i][j][x][y]+(ny?c[j+1]:0));
}
最后的答案就是 \(f_{n,m}\) 中的最小值。
时间复杂度：\(O(n \cdot m)\)
const int N=2100,INF=1e18;
bool a[N][N];int ans=INF,n,m;
int f[N][N][2][2];vi r,c;
void sol(){
f[1][1][0][0]=0;f[1][1][1][0]=r[1];
f[1][1][0][1]=c[1];f[1][1][1][1]=r[1]+c[1];
L(i,1,n) L(j,1,m) L(x,0,1) L(y,0,1) L(nx,0,1) L(ny,0,1){
if(i+1<=n&&(a[i][j]^x^y==a[i+1][j]^nx^ny)&&y==ny)
f[i+1][j][nx][ny]=min(f[i+1][j][nx][ny],f[i][j][x][y]+(nx?r[i+1]:0));
if(j+1<=m&&(a[i][j]^x^y==a[i][j+1]^nx^ny)&&x==nx)
f[i][j+1][nx][ny]=min(f[i][j+1][nx][ny],f[i][j][x][y]+(ny?c[j+1]:0));
}
}void work(){
cin>>n>>m;r.resize(n+1),c.resize(m+1);string s;
L(i,1,n) cin>>r[i];L(i,1,m) cin>>c[i];
L(i,1,n){cin>>s;L(j,1,m) a[i][j]=(s[j-1]=='1');}
me(f,0x7f);sol();
cout<<min({f[n][m][0][0],f[n][m][1][0],f[n][m][0][1],f[n][m][1][1]});
}
G
字符串转图论。
如果设 \(f_{a,b}\) 为以 \(a,b\) 结尾的所有字符串的最大权值。
那么有 \(f_{a,b}+cost_{abc}+cost_{ab}+cost_{c} \xrightarrow{\max} f_{b,c}\)
这样，点数 \(O(\left\vert \sum \right\vert ^2)\)，边数\(O(\left\vert \sum \right\vert ^3)\)，跑 SPFA 即可。
**时间复杂度：\(O(\left\vert \sum \right\vert ^5)\)。
#define ch(i) (i-'a')
#define F(i) (i).first
#define S(i) (i).second
#define si(i) ((int)i.size())
#define me(t,x) memset(t,x,sizeof(t))
#define pi pair<int,int>
#define L(i,j,k) for(int (i)=(j);i<=(k);(i)++)
using namespace std;const int N=31;bool vis[N][N];
int w1[N],w2[N][N],w3[N][N][N],dis[N][N],cnt[N][N];
void work(){
int n;cin>>n;me(dis,128);L(i,1,n){
string s;cin>>s;int x;cin>>x;
if(si(s)==1) w1[ch(s[0])]=x;
else if(si(s)==2) w2[ch(s[0])][ch(s[1])]=x;
else w3[ch(s[0])][ch(s[1])][ch(s[2])]=x;
}queue<pi>q;q.push({26,26});dis[26][26]=0;
int ans=dis[0][0];
while(!q.empty()){
int u=F(q.front()),v=S(q.front());q.pop();vis[u][v]=0;
L(c,0,25){
int now=dis[u][v]+w1[c]+w2[v][c]+w3[u][v][c];
if(now>dis[v][c]){
ans=max(ans,now);
dis[v][c]=now;cnt[v][c]=cnt[u][v]+1;
if(cnt[v][c]>=n) return cout<<"Infinity",void();
if(!vis[v][c]) vis[v][c]=1,q.push({v,c});
}
}
}cout<<ans;
}
Ex
