CF1072A Golden Plate
第 \(i\) 个矩形的周长为 \(2(w - 4(i - 1))+2(h - 4(i - 1))-4\)，枚举 \(i\) 求和。
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,k;
int main()
{
scanf("%d%d%d",&n,&m,&k);
int ans=0;
for(int i=1;i<=k;i++)
ans+=2*(n-4*(i-1))+2*(m-4*(i-1))-4;
printf("%d",ans);
return 0;
}
CF1072B Curiosity Has No Limits
令 \(f_{i,j}\) 表示考虑前 \(i\) 个数，\(a_i=j\) 是否合法，直接枚举 \(a_i\) 转移。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
int n;
int t[N];
int a[N],b[N];
bool f[N][4];
void print(int u,int j)
{
if(u==n)
{
printf("%d ",j);
return;
}
printf("%d ",j);
for(int k=0;k<=3;k++)
if((j|k)==a[u]&&(j&k)==b[u]&&f[u+1][k]) print(u+1,k);
return;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n-1;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n-1;i++)
scanf("%d",&b[i]);
f[n][0]=f[n][1]=f[n][2]=f[n][3]=true;
for(int i=n-1;i>=1;i--)
for(int j=0;j<=3;j++)
if(f[i+1][j])
{
for(int k=0;k<=3;k++)
if((j|k)==a[i]&&(j&k)==b[i]) f[i][k]=true;
}
for(int j=0;j<=3;j++)
if(f[1][j])
{
printf("YES\n");
print(1,j);
return 0;
}
printf("NO");
return 0;
}
CF1072C Cram Time
可以发现，一定看的是 \(1\sim k\) 的笔记。方案大概是从大到小枚举，如果 \(A\) 剩下的时间 \(\ge i\)，分配到 \(A\)，否则分配到 \(B\)，可以证明一定可以将 \(A\) 填满。
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int a,b;
int main()
{
scanf("%d%d",&a,&b);
int k=0;
for(int i=1;;i++)
if(1LL*i*(i+1)/2<=a+b) k=max(k,i);
else break;
vector<int>d1,d2;
for(int i=k;i>=1;i--)
if(a>=i) d1.emplace_back(i),a-=i;
else if(b>=i) d2.emplace_back(i),b-=i;
else exit(1);
int n=d1.size(),m=d2.size();
printf("%d\n",n);
for(int u:d1)
printf("%d ",u);
printf("\n");
printf("%d\n",m);
for(int u:d2)
printf("%d ",u);
return 0;
}
CF1072D Minimum path
将路径前 \(k\) 个不是 a 的字符变成 a，就变成了 \(k=0\) 的情况。
\(k=0\) 的情况贪心 BFS，每次记录下当前字典序最小的点，每次拓展字典序最小的位置即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=2005;
const int dir[2][2]={{1,0},{0,1}};
int n,k;
char s[N][N];
int f[N][N];
queue<pair<int,int>>q;
bool vis[N][N];
void solve()
{
vector<pair<int,int>>nxt;
char c='z';
while(!q.empty())
{
auto [x,y]=q.front();
q.pop();
for(int i=0;i<2;i++)
{
int tx=x+dir[i][0],ty=y+dir[i][1];
if(tx<1||tx>n||ty<1||ty>n) continue;
if(tx==n&&ty==n)
{
printf("%c",s[tx][ty]);
exit(0);
}
if(vis[tx][ty]) continue;
c=min(c,s[tx][ty]);
vis[tx][ty]=true;
nxt.emplace_back(tx,ty);
}
}
printf("%c",c);
for(auto [x,y]:nxt)
{
if(s[x][y]==c) q.emplace(x,y);
vis[x][y]=false;
}
return;
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)
scanf("%s",s[i]+1);
if(k==0)
{
if(n==1)
{
printf("%c",s[1][1]);
return 0;
}
q.emplace(1,1);
printf("%c",s[1][1]);
while(true)
solve();
return 0;
}
memset(f,63,sizeof(f));
f[1][1]=0;
int m=0;
vector<pair<int,int>>nxt;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
if(i-1>=1) f[i][j]=min(f[i][j],f[i-1][j]);
if(j-1>=1) f[i][j]=min(f[i][j],f[i][j-1]);
if(s[i][j]!='a') f[i][j]++;
if(f[i][j]==k) m=max(m,i+j-1),nxt.emplace_back(i,j);
}
if(f[n][n]<=k)
{
for(int i=1;i<=2*n-1;i++)
printf("a");
return 0;
}
for(auto [x,y]:nxt)
if(x+y-1==m) q.emplace(x,y);
for(int i=1;i<=m;i++)
printf("a");
while(true)
solve();
return 0;
}
CF1072E Triple Flips
咕咕咕
CF1072F Familiar Operations
可以发现，操作过程中的数最多不会超过 \(\operatorname{lcm}(a,b)\)，令 \(P\) 为操作过程中的某个数，\(P=\prod {p_i}^{c_i}\)，我们可以搜出所有 \(c_i\) 的情况，\(\prod (c_i+1)\) 相等相当于两个数的因数个数相等。可以发现，这种情况不会太多。
我们可以将一种 \(c_i\) 的情况看做一个点，建立图论模型，我们可以求出某个点到某种因数个数经过最少的距离。查询时枚举到最终到哪种因数个数，然后算下两边的距离相加。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<algorithm>
using namespace std;
const int N=1000005,M=5005;
const long long MAX=1e12;
int T;
bool isprime[N];
int prime[N],tot;
void init(int n=1000000)
{
memset(isprime,true,sizeof(isprime));
isprime[1]=false;
for(int i=2;i<=n;i++)
{
if(isprime[i]) prime[++tot]=i;
for(int j=1;j<=tot&&i*prime[j]<=n;j++)
{
isprime[i*prime[j]]=false;
if(i%prime[j]==0) break;
}
}
return;
}
long long mul(long long a,long long b)
{
__int128 c=(__int128)a*b;
if(c>MAX) return MAX+1;
else return c;
}
long long ksm(long long a,long long b)
{
long long res=1;
while(b)
{
if(b&1) res=mul(res,a);
a=mul(a,a),b>>=1;
}
return res;
}
vector<int>state[M];
int m;
map<vector<int>,int>pos;
int factor[M];
int b[M],num;
void dfs(vector<int>now,long long sum,int fac)
{
if(sum>MAX) return;
if(pos[now]) return;
m++;
state[m]=now;
factor[m]=fac;
b[++num]=fac;
pos[now]=m;
int lim=now.empty()?40:now.back();
for(int i=1;i<=lim;i++)
{
vector<int>nxt=now;
nxt.emplace_back(i);
dfs(nxt,mul(sum,ksm(prime[nxt.size()],i)),fac*(i+1));
}
return;
}
vector<int>G[M];
void add(int s)
{
vector<int>&val=state[s];
for(size_t i=0;i<val.size();i++)
{
vector<int>nxt;
for(size_t j=0;j<i;j++)
nxt.emplace_back(val[j]);
if(val[i]-1>0) nxt.emplace_back(val[i]-1);
for(size_t j=i+1;j<val.size();j++)
nxt.emplace_back(val[j]);
sort(nxt.begin(),nxt.end(),greater<int>());
if(pos[nxt]) G[s].emplace_back(pos[nxt]);
nxt.clear();
for(size_t j=0;j<i;j++)
nxt.emplace_back(val[j]);
nxt.emplace_back(val[i]+1);
for(size_t j=i+1;j<val.size();j++)
nxt.emplace_back(val[j]);
sort(nxt.begin(),nxt.end(),greater<int>());
if(pos[nxt]) G[s].emplace_back(pos[nxt]);
}
vector<int>nxt=val;
nxt.push_back(1);
if(pos[nxt]) G[s].emplace_back(pos[nxt]);
return;
}
void bfs(int s,int *dis)
{
static bool vis[M];
for(int i=1;i<=m;i++)
vis[i]=false,dis[i]=m+1;
dis[s]=0;
vis[s]=true;
queue<int>q;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
for(int v:G[u])
{
if(vis[v]) continue;
dis[v]=dis[u]+1;
vis[v]=true;
q.push(v);
}
}
return;
}
vector<int>divide(int x)
{
vector<int>res;
for(int i=1;i<=tot&&prime[i]<=sqrt(x);i++)
if(x%prime[i]==0)
{
int cnt=0;
while(x%prime[i]==0) x/=prime[i],cnt++;
res.emplace_back(cnt);
}
if(x!=1) res.emplace_back(1);
sort(res.begin(),res.end(),greater<int>());
return res;
}
int dis[M][M];
int f[M][M];
void solve()
{
int a,b;
scanf("%d%d",&a,&b);
vector<int>p=divide(a),q=divide(b);
int s=pos[p],t=pos[q];
int ans=m;
for(int u=1;u<=num;u++)
ans=min(ans,f[s][u]+f[t][u]);
printf("%d\n",ans);
return;
}
int main()
{
init();
dfs({},1,1);
for(int i=1;i<=m;i++)
add(i);
for(int i=1;i<=m;i++)
{
sort(G[i].begin(),G[i].end());
G[i].erase(unique(G[i].begin(),G[i].end()),G[i].end());
}
for(int i=1;i<=m;i++)
bfs(i,dis[i]);
sort(b+1,b+num+1);
num=unique(b+1,b+num+1)-b-1;
for(int i=1;i<=m;i++)
factor[i]=lower_bound(b+1,b+num+1,factor[i])-b;
memset(f,63,sizeof(f));
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
f[i][factor[j]]=min(f[i][factor[j]],dis[i][j]);
scanf("%d",&T);
while(T--)
solve();
return 0;
}