USACO22 JAN 做题记录
Cu
T1
暴力题。
#include
#include
using namespace std;
const int maxk=27;
int ans1,ans2;
int cnt[maxk],ok[4][4];
string s[4],t[4];
int main(){
cin>>s[1]>>s[2]>>s[3]>>t[1]>>t[2]>>t[3];
for(int i=1;i<=3;i++)
for(int j=0;j<3;j++){
if(s[i][j]==t[i][j])
ans1++,ok[i][j]=1;
else cnt[s[i][j]-64]++;
}
for(int i=1;i<=3;i++)
for(int j=0;j<3;j++)
if(ok[i][j]==0&&cnt[t[i][j]-64])
cnt[t[i][j]-64]--,ans2++;
printf("%d\n%d\n",ans1,ans2);
return 0;
}
T2
暴力题。
#include
#include
using namespace std;
int T;
int a[3][5];
int calc(int x,int y){
int win=0,lose=0;
for(int i=1;i<=4;i++)
for(int j=1;j<=4;j++)
win+=a[x][i]>a[y][j],lose+=a[x][i]lose;
}
int main(){
scanf("%d",&T);
while(T--){
int ans=0;
scanf("%d%d%d%d%d%d%d%d",&a[0][1],&a[0][2],&a[0][3],&a[0][4],&a[1][1],&a[1][2],&a[1][3],&a[1][4]);
if(calc(0,1)==0)
for(int i=1;i<=4;i++)
swap(a[0][i],a[1][i]);
if(calc(0,1)==0){
puts("no");
continue;
}
for(int i=1;i<=10;i++)
for(int j=i;j<=10;j++)
for(int k=j;k<=10;k++)
for(int l=k;l<=10;l++){
a[2][1]=i,a[2][2]=j,a[2][3]=k,a[2][4]=l;
if(calc(1,2)&&calc(2,0))
ans=1;
}
puts(ans==1? "yes":"no");
}
return 0;
}
T3
好难。
相邻减一相当于把 \(x\) 位置的差分数组加一，\(x-2\) 位置的差分数组减一，还有两种特殊情况，一个是位置 \(3\) 加一，一个是位置 \(n-2\) 减一。
从后往前模拟即可，时间复杂度 \(O(n)\)。
#include
#include
const int maxn=100005;
int T,n;
int a[maxn];
long long b[maxn];
inline int min(int a,int b){
return a=2;i--){
if(b[i]>0)
if(((n-i)&1)==0)
flg=1;
if(b[i]<0)
b[i-2]+=b[i];
}
for(int i=1;i<=n;i++)
ans+=a[i]-b[1];
if(b[1]<0||b[0]<0||flg)
puts("-1");
else printf("%lld\n",ans);
b[0]=0;
}
return 0;
}
Ag
T1
感觉是全场最困难的题目。
考虑最优的行动是分四段：
先加若干次，然后若干个除（若当前数末尾是一，则先进行一次加），再加若干次，然后再是若干个乘（若目标数末尾是一，则之后进行一次加）。
直接枚举每次操作次数即可，复杂度 \(O(\log n)\)。
#include
int T,ans;
long long A,B;
int main(){
scanf("%d",&T);
while(T--){
scanf("%lld%lld",&A,&B),ans=10000;
for(int i=0;i<=10;i++)
for(int j=0;j<=60;j++)
for(int k=0;k<=10;k++){
int res=i;
long long now=A+i;
for(int p=1;p<=j;p++){
if(now&1)
now++,res++;
now>>=1,res++;
}
now+=k,res+=k;
int tot=0;
long long tmp=now;
while((tmp<<1)<=B)
tmp<<=1,tot++;
if((B>>tot)!=now)
continue;
for(int p=1;p<=tot;p++){
now<<=1,res++;
if((B>>(tot-p))&1)
now++,res++;
}
if(res T2
签到题。
考虑满足 \(\forall_{i
复杂度 \(O(n)\)。
#include
const int maxn=300005;
int n,top;
int h[maxn],lc[maxn],rc[maxn],stk[maxn],totl[maxn],totr[maxn];
long long ans;
long long suml[maxn],sumr[maxn];
void dfs(int x){
if(lc[x]){
dfs(lc[x]),ans+=1ll*totr[lc[x]]*(x+1)-sumr[lc[x]];
totl[x]=totl[lc[x]]+1,suml[x]=suml[lc[x]]+x;
}
else suml[x]=x,totl[x]=1;
if(rc[x]){
dfs(rc[x]),ans+=suml[rc[x]]-1ll*totl[rc[x]]*(x-1);
totr[x]=totr[rc[x]]+1,sumr[x]=sumr[rc[x]]+x;
}
else sumr[x]=x,totr[x]=1;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&h[i]);
int k=top;
while(k>0&&h[stk[k]]<=h[i])
k--;
if(k>0)
rc[stk[k]]=i;
if(k T3
有一点点困难。
考虑将一只奶牛最喜欢的两种麦片连边，对于每个连通块，其答案的上界一定是点数和边数的 \(\max\)，下面给出一种构造：
找这个连通块的一个 dfs 树，找到其一个环（若没有则任意钦定一个单点），先取环上的一条边，那么剩下的边都可以按顺序取。然后从这个环（点）向外搜索出一个基环树（树）的形态即可。
复杂度 \(O(n)\)。
#include
#include
#include
#include
#include
using namespace std;
const int maxn=200005;
int n,m,ans,flg;
int vis[maxn],vvis[maxn],ok[maxn],fa[maxn],rec[maxn],fir[maxn],sec[maxn],dep[maxn],tr[maxn];
vectortmp,V,res,v[maxn],w[maxn];
queueq;
inline void add(int x,int y,int i){
v[x].push_back(y),w[x].push_back(i);
}
void dfs(int x,int last){
fa[x]=last,vis[x]=1,dep[x]=dep[last]+1;
for(int i=0;i Au
T1
太困难了。
时光倒流，相当于一开始所有数相等，你每次给相邻位置加一，每个位置不能超过上界，求能得到多少序列。
假设所有数的初值是固定的（设其为 \(st\)），我们就可以直接 dp，令 \(f_{i,j}\) 表示选到第 \(i\) 个位置，其中 \((i,i+1)\) 选了 \(j\) 次的合法序列数，那么可以得到：
\[f_{i+1,k}=\sum_{j=0}^{\min\{h_i-st,h_{i+1}-st-k\}} f_{i,j} \]前缀和优化即可做到 \(O(nV)\)。
当 \(n\) 为偶数的时候，\(st\) 可以直接是 \(0\)，否则 \(st\) 可以设为 \(0,1,\cdots,\min h_i\) 的任意数。
总时间复杂度 \(O(nV^2)\)。
#include
#include
#include
using namespace std;
const int maxn=105,maxv=1005,mod=1000000007;
int n,ans,up,mn=100000;
int h[maxn],f[maxn][maxv],g[maxn][maxv];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&h[i]),mn=min(mn,h[i]);
h[n+1]=maxv-1;
if(n%2==0)
up=0;
else up=mn;
for(int st=0;st<=up;st++){
memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
for(int i=0;i<=h[1]-st&&i<=h[2]-st;i++)
f[1][i]=1;
for(int i=1;i T2
漏看了一个条件，居然还做出来了。
考虑时光倒流，然后线段树分治，那么我们对于每个数，找到其第一次合法的时间。
我们将每个点拆点，\(A\) 和 \(B\)，初始一个点的 \(A\) 和 \(B\) 连边。合并两个并查集先特判是否有一个连通块是合法的，然后将两个并查集的 \(A\) 连边，撤销的时候给边懒删除即可。
当一个点变成 active 之后，我们就将整个连通块遍历一遍，将遍历到的 \(B\) 点统计答案，并将整个连通块清空，这样可以均摊分析，时间复杂度为 \(O(n\log n\alpha(n))\)。
代码有些细节写错了，但是没有把我卡掉，我就懒得改了。
#include
#include T3
赛场不会。
令题面中 \(j\) 数组为 \(b\) 数组。
首先有一个简单的差分约束：
\[a_i\geqslant a_{i-1}\\a_{b_i}-a_i\leqslant k\\a_{b_i+1}-a_i>k \]可以发现 \(k\) 越大一定是越优的，于是我们直接令 \(k=10^9\)，设 \(a_i=x_ik+y_i\)（\(0\leqslant y_i
上面的差分约束可以转化为：
\(x_i-x_{i-1}\geqslant 0\)，若 \(x_i-x_{i-1}=0\)，则有 \(y_i-y_{i-1}\geqslant 0\)。
\(x_i-x_{b_i}\geqslant -1\)，若 \(x_i-x_{b_i}=-1\)，则有 \(y_i-y_{b_i}\geqslant 0\)。
\(x_{b_i+1}-x_i\geqslant 1\)，若 \(x_{b_i+1}-x_i=1\)，则有 \(y_{b_i+1}-y_i\geqslant 1\)
我们可以考虑先构造出 \(x\)，再通过 \(x\) 构造一个差分约束模型，不难发现由于边权是 \(0/-1\) 且没有负环，所以所有环都是零环，缩点+拓扑排序即可解决。
事实上很容易给出一组 \(x\) 的构造：
令变量 \(p=1\)，并不断执行以下操作：
设当前轮数为 \(d\)，将 \([p,b_p]\) 设为 \(d\)，再令 \(p\leftarrow b_p+1\)。
第一个限制和第三个限制显然满足，考虑为什么满足第二个限制：
我们设覆盖位置 \(i\) 的 \(p\) 为 \(p_0\)，则由于 \(b_{p_0}\geqslant i\)，而 \(b\) 又是递增的，所以有 \(b_{b_{p_0}+1}\geqslant b_i\)，也就是至多下一轮 \(b_i\) 就会被覆盖。
时间复杂度 \(O(n)\)。
#include
#include
#include
using namespace std;
const int maxn=100005,K=1000000000;
int n,top,dfns,tot,es;
int b[maxn],X[maxn],Y[maxn],deg[maxn],stk[maxn],dfn[maxn],low[maxn],vis[maxn],bel[maxn],xx[maxn*3],yy[maxn*3],zz[maxn*3];
queueq;
vectorv[maxn],g[maxn];
inline void add(int x,int y,int z){
if(z==0)
v[x].push_back(y);
es++,xx[es]=x,yy[es]=y,zz[es]=z;
}
void tarjan(int x){
dfn[x]=low[x]=++dfns,vis[x]=1,stk[++top]=x;
for(int i=0;i