Codeforces 1009
hack好给力啊233
A.Game Shopping
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
const int N=1e3+5;
int n,m,cost[N],A[N];
inline int read()
{
register int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
int main()
{
n=read(), m=read();
for(int i=1; i<=n; ++i) cost[i]=read();
for(int i=1; i<=m; ++i) A[i]=read();
int now=1,ans=0;
for(int i=1; i<=n && now<=m; ++i)
if(cost[i]<=A[now]) ++ans, ++now;
printf("%d\n",ans);
return 0;
}
B.Minimum Ternary String
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
const int N=1e5+7;
int n;
char s[N],ans[N];
int main()
{
scanf("%s",s+1), n=strlen(s+1);
int cnt[5],now;
cnt[0]=cnt[1]=cnt[2]=0;
for(now=1; now<=n; ++now)
if(s[now]!='2') ++cnt[s[now]-'0'];
else break;
for(int i=1; i<=cnt[0]; ++i) ans[i]='0';
for(int i=cnt[0]+1; i<=cnt[0]+cnt[1]; ++i) ans[i]='1';
cnt[0]=cnt[1]=cnt[2]=0;
for(int i=now; i<=n; ++i) ++cnt[s[i]-'0'];
for(int i=now; i<now+cnt[1]; ++i) ans[i]='1';
s[n+1]='3';
for(int i=now+cnt[1]; i<=n; ++i)
{
while(s[now]=='1') ++now;
ans[i]=s[now++];
}
puts(ans+1);
return 0;
}/*
102012012
*/
C.Annoying Present
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define eps 1e-8
typedef long long LL;
const int N=1e5+7;
inline int read()
{
register int now=0,f=1;register char c=gc();
for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now*f;
}
int main()
{
int n=read(), m=read();
LL sum=0, sumX=0, C1, C2=1ll*n*(n-1)>>1;//n/2写成n>>1略显乱
if(n&1) C1=1ll*(n>>1)*((n>>1)+1);
else C1=1ll*(n>>1)*((n>>1)+1)-1ll*(n>>1);
LL x,d;
for(int i=1; i<=m; ++i)
{
x=read(), d=read(), sumX+=x;
if(d>0) sum+=C2*d;
else if(d<0) sum+=C1*d;
}
printf("%.8lf",1.0*(sum+1ll*n*sumX)/n);
return 0;
}
D.Relatively Prime Graph
靠 欺负我读英文题目不仔细吗 图必须连通。。
于是WA*3。看了数据才A。。
这破题 rank1000+了啊啊啊
而且这题n^2纯暴力都能过 太没意思了吧
#include <cmath>
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define pr std::pair<int,int>
#define mp std::make_pair
const int N=1e5+7;
int n,m,cnt,P[N],fac[N],sum;
pr A[3000005];
bool not_P[N];
int gcd(int x,int y){
return y?gcd(y,x%y):x;
}
void Pre(int n)
{
for(int i=2; i<=n; ++i)
{
if(!not_P[i]) P[++cnt]=i;
for(int j=1; j<=cnt&&i*P[j]<=n; ++j)
{
not_P[i*P[j]]=1;
if(!(i%P[j])) break;
}
}
for(int i=2; i<=n; ++i)
if(!not_P[i]) fac[i]=i;
else{
for(int j=2; j<=i; ++j)
if(!(i%j)) {fac[i]=j; break;}
}
}
int main()
{
scanf("%d%d",&n,&m);// printf("%d\n",m);
if(m<n-1) return puts("Impossible"),0;//...
Pre(n);
for(int i=2; i<=n && sum<m; ++i) A[++sum]=mp(1,i);
for(int x=1; x<=cnt && sum<m; ++x)
{
int i=P[x];
for(int j=i+1; j<=n && sum<m; )
{
int k=std::min(j+fac[i]-1,n+1);//n+1!
for(int l=j; l<k && sum<m; ++l) A[++sum]=mp(i,l);
j=k+1;
}
}
for(int i=4; i<=n && sum<m; ++i)
{
if(!not_P[i]) continue;
for(int j=i+1; j<=n && sum<m; )
{
int k=std::min(j+fac[i]-1,n+1);
for(int l=j; l<k && sum<m; ++l)
if(gcd(i,l)==1) A[++sum]=mp(i,l);
j=k+1;
}
}
if(sum<m) puts("Impossible");
else
{
puts("Possible");
for(int i=1; i<=m; ++i)
printf("%d %d\n",A[i].first,A[i].second);
}
return 0;
}
比赛结束后
E.Intercity Travelling(递推)
\(Description\)
Leha从0出发前往n。给定数组\(a[]\)。路上可能会有一些休息点，Leha会在这些地方停下休息。如果当前所在休息点\(i\)，而上一个休息点是\(j\)，那他会得到\(a_{i-j}\)的困难值（包括在n点停下也要计算，路程上所有累加）。休息点一共有\(2^{n-1}\)种可能分布，求所有可能中整段路程所得到的困难值的期望\(e\times 2^{n-1}\mod\ 998244353\)。
\(Solution\)
要求一个线性做法，我们尝试递推求它。
对每一个位置\(i\)，我们可以写出它作为休息点时得到困难值的期望：\(e_i=\frac{a_1}{2}+\frac{a_2}{2^2}+\ldots+\frac{a_{i-1}}{2^{i-1}}+\frac{a_i}{2^{i-1}}\)。最后一项的概率是\(2^{i-1}\)，因为是从0号点出发。
那么就可以得到\(e_1=a_1，e_{i+1}=e_i-\frac{a_i}{2^i}+\frac{a_{i+1}}{2^i}\)。
//93ms 7700KB
#include <cstdio>
#include <cctype>
#define gc() getchar()
#define mod (998244353)
const int N=1e6+5;
int n,A[N],pw[N];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
int main()
{
n=read();
for(int i=1; i<=n; ++i) A[i]=read();
pw[0]=1;
for(int i=1; i<=n; ++i) pw[i]=pw[i-1]<<1, pw[i]>=mod&&(pw[i]-=mod);
long long now=1ll*A[1]*pw[n-1]%mod, ans=now;
for(int i=1; i<n; ++i)
{
now=(now-1ll*A[i]*pw[n-1-i]%mod+1ll*A[i+1]*pw[n-1-i]%mod+mod)%mod,
ans+=now;
}
printf("%I64d\n",ans%mod);
return 0;
}
F.Dominant Indices(启发式合并)
显然对于\(d_{x,i}\)，我们有\(d_{x,i}=\sum_{v=son[x]}d_{v,i-1}\)
Dominant Indices就是最大的\(d_{x,i}\)中下标最小的\(i\)。我们可以利用启发式合并求\(d_x\)。启发式合并一般的复杂度是\(O(n\log n)\)的，但在本题中，复杂度只与深度较小的点的深度有关，而不是点数。所以复杂度是\(O(n)\)的。
我们还需要将数组整体右移，以便插入一个\(d_{x,0}=1\)。可以用map(\(O(n\log n)\))，也可以用vector倒序存储，这样就是\(O(n)\)的了。
也可以直接用个大点的(\(O(n)\)其实就够了)数组，每个点维护在数组中的位置。
[Update]这就是dsu on tree或者长链剖分啊。
//546ms 89700KB
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
const int N=1e6+5;
int n,Enum,H[N],nxt[N<<1],to[N<<1],Ans[N],A[N],pos[N],len[N],mx[N],mxpos[N];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline void AddEdge(int u,int v)
{
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;
}
void Merge(int x,int y)//x<-y
{
if(len[x]<len[y])
{
std::swap(pos[x],pos[y]), std::swap(len[x],len[y]),
std::swap(mx[x],mx[y]), std::swap(mxpos[x],mxpos[y]);
}
for(int i=0,ly=len[y],px=pos[x],py=pos[y]; i<ly; ++i)
{
A[px+i]+=A[py+i]; //A[px+i+1]+=A[py+i];
if(A[px+i]>mx[x]) mx[x]=A[px+i], mxpos[x]=i;
else if(A[px+i]==mx[x] && i<mxpos[x]) mxpos[x]=i;
}
}
void DFS(int x,int f)
{
A[pos[x]]=1, len[x]=1, mx[x]=1, mxpos[x]=0;
for(int v,i=H[x]; i; i=nxt[i])
if((v=to[i])!=f)
{
pos[v]=pos[x]+len[x]+1, DFS(v,x);//给v腾出一位，合并前将v右移一位。否则len[x]==len[v]时会重叠。。
A[--pos[v]]=0, ++len[v], ++mxpos[v], Merge(x,v);
}
Ans[x]=mxpos[x];
}
int main()
{
n=read();
for(int i=1; i<n; ++i) AddEdge(read(),read());
pos[1]=1, DFS(1,1);
for(int i=1; i<=n; ++i) printf("%d\n",Ans[i]);
return 0;
}
G.Allowed Letters(Hall定理 位运算)
\(Description\)
给定长为n、由小写字母a~f组成的字符串s。有m个限制，每个限制为：在\(pos_i\)处只能是某些字母(\(pos_i\)两两不同)。
你可以任意交换原串两个字母的位置，问是否能得到满足限制的串，若能，输出满足限制的最小字典序的字符串。
\(Solution\)
有n个字符，每个字符可以放在某些位置，要求这些字符全部放置->完备匹配。
可以跑网络流，检查最大流是否等于n，连边比较好想。然后假设想要让i位置放字符c，如果原最大流不需要c->i这条边，那么可以；否则让这条边退流，容量-1，再检查最大流是否等于n。
如果决定了位置i放字符c，那么要使c->i这条边的容量-1.
没写，万一调不出来有点。。Tutorial里说复杂度\(O(n*2^A*A^2)\)(A为字符集大小)，不知道\(2^A\)是为什么。。（好像也是判子集合法？）
可以考虑Hall定理。对于任意一个字符的子集，其中字符个数要<=能够匹配其中字符的位置个数。
这样的话对于同一种字符，显然只需要检验包含它最多的子集（位置数不会变）。所以我们要检查的子集只有\(2^A=64\)个(A为字符集大小)。
任意子集包含字符的个数sum可以\(O(A*2^A)\)或\(O(2^A)\)算。对于(只要)能够匹配某子集s中任意字符 的位置数我们可以去算：位置总数-只能匹配除s中字符外的位置数。
除s中字符外的子集可以表示为2^A-1-s，预处理其包含的所有子集的位置数即可，记为f[]。
如果现在要确定i位置放什么，那要先减掉i对f的贡献，即枚举所有包括 位置i可放字符子集 的子集，依次-1。要放某字符首先要能放，然后数量-1，再Check就行了。
//62ms 400KB
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
#define lb(i) (i&-i)
const int N=1e5+7;
int n,num[7],can[N],sum[69],f[69],bit[69];
char s[N],tmp[N];
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
bool Check()
{
for(int i=1; i<64; ++i)
{
sum[i]=sum[i^lb(i)]+num[bit[lb(i)]];
if(sum[i]>f[63]/*not n，or n也-1*/-f[63-i]) return 0;
}
return 1;
}
int main()
{
scanf("%s",s+1), n=strlen(s+1);
for(int i=1; i<=n; ++i) can[i]=63, ++num[s[i]-'a'];
for(int m=read(),p; m--; )
{
can[p=read()]=0, scanf("%s",tmp+1);
for(int j=1,l=strlen(tmp+1); j<=l; ++j)
can[p]|=1<<tmp[j]-'a';
}
for(int i=1; i<=n; ++i) ++f[can[i]];
for(int i=0; i<6; ++i)//求其包含的所有子集 先枚举i！
for(int j=1; j<64; ++j)
if(j>>i & 1)
f[j]+=f[j^(1<<i)];
for(int i=0; i<6; ++i) bit[1<<i]=i;
if(!Check()) return puts("Impossible"),0;
for(int i=1; i<=n; ++i)
{
for(int s=can[i]; s<=63; s=(s+1)|can[i]) --f[s];
for(int j=0; j<6; ++j)
{
if(!(can[i]>>j&1)) continue;
--num[j];
if(Check()) {putchar(j+'a'); break;}
++num[j];
}
}
return 0;
}