Preface
万恶的psk搬的全是Atcoder上的题目,然后理所当然的后面题目全是Counting Problem了
作为计数苦手直接当场暴毙,3h写完前面的8个题然后直接跑路
AtCoder arc148_a mod M
开场差点被签到腐乳了,没发现答案不是\(1\)就是\(2\)直接傻掉了
由于\(M=2\)时答案至多为\(2\),因此只需考虑什么情况下答案为\(1\)即可
这是个经典问题,对于两个数\(x,y\),当\(M\mid \operatorname{abs}(x-y)\)时\(x\equiv y\pmod M\)
#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,a[N],g,c[2];
int main()
{
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
for (i=2;i<=n;++i) g=__gcd(g,abs(a[i]-a[1]));
return puts(g!=1?"1":"2"),0;
}
AtCoder arc108_a Sum and Product
纯签到题,枚举即可
#include<cstdio>
#include<iostream>
#define int long long
#define RI register int
#define CI const int&
using namespace std;
int S,P;
signed main()
{
scanf("%lld%lld",&S,&P);
for (RI x=1;x*x<=P;++x) if (P%x==0)
{
int y=P/x; if (x+y==S) return puts("Yes"),0;
}
return puts("No"),0;
}
AtCoder arc148_b dp
顶针题,不难发现从左边开始的第一个p
一定要成为操作的左端点,否则一定不优
然后大力枚举右端点大力判断即可,复杂度\(O(n^2)\)
#include<cstdio>
#include<iostream>
#include<string>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
int n; string s,ans;
int main()
{
RI i,j; int pos=-1; for (cin>>n>>s,i=0;i<n;++i) if (s[i]=='p') { pos=i; break; }
if (pos==-1) return cout<<s,0;
for (ans=s,i=pos+1;i<=n;++i)
{
string t=s; reverse(t.begin()+pos,t.begin()+i);
for (j=pos;j<i;++j) t[j]=(t[j]=='d'?'p':'d');
ans=min(ans,t);
}
return cout<<ans,0;
}
AtCoder arc108_b Abbreviate Fox
顶针题,不难发现遇到fox
能删就删一定不劣,因此直接拿个栈模拟一下即可
#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005;
int n,top; char s[N],stk[N];
int main()
{
RI i; for (scanf("%d%s",&n,s+1),i=1;i<=n;++i)
{
stk[++top]=s[i];
while (top>=3&&stk[top-2]=='f'&&stk[top-1]=='o'&&stk[top]=='x') top-=3;
}
return printf("%d",top),0;
}
AtCoder arc148_c Lights Out on Tree
找了个感觉很优秀的性质,没想到差点把自己玩没了
不妨把询问包含的点称为黑点,原来的点称为白点
手玩一波会发现操作次数等于两端颜色不同的边数,如果根节点是黑点那么还需要额外加\(1\)(因为其实前面那个条件等价于把整棵树颜色变成相同的)
考虑这个玩意怎么统计,YY了好久也没想到什么好的做法,后面无奈滚去写根号分治了
当询问的点数超过\(\sqrt{200000}\)时,直接把整棵树扫一遍即可;否则我们可以暴力遍历所有黑点点对来算答案
后面一问祁神发现原来有很trivial的做法,顿感我是个傻逼
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,S=400;
int n,x,q,deg[N],col[N]; vector <int> v[N]; unordered_set <int> son[N];
int main()
{
//freopen("E.in","r",stdin); freopen("E.out","w",stdout);
RI i,j; for (scanf("%d%d",&n,&q),i=2;i<=n;++i)
scanf("%d",&x),v[x].push_back(i),++deg[x],++deg[i],son[x].insert(i);
while (q--)
{
scanf("%d",&x); vector <int> p(x); int ans=0;
for (i=0;i<x;++i) scanf("%d",&p[i]); sort(p.begin(),p.end());
if (x<=S)
{
for (i=0;i<x;++i) for (j=i+1;j<x;++j)
if (son[p[i]].count(p[j])) --deg[p[i]],--deg[p[j]];
for (i=0;i<x;++i) ans+=deg[p[i]];
for (i=0;i<x;++i) for (j=i+1;j<x;++j)
if (son[p[i]].count(p[j])) ++deg[p[i]],++deg[p[j]];
} else
{
for (i=1;i<=n;++i) col[i]=0;
for (i=0;i<x;++i) col[p[i]]=1;
for (i=1;i<=n;++i) for (auto j:v[i]) ans+=(col[i]!=col[j]);
}
printf("%d\n",ans+(p[0]==1));
}
return 0;
}
AtCoder arc108_c Keep Graph Connected
遇到这种给出了一个图但是保证联通性的题目,很容易想到直接把图扔掉放到生成树上做
考虑自顶向下确定每个点的值,首先先随便给根节点搞个颜色,然后枚举每条树边
- 若当前点颜色和这条边颜色相同,则给其子节点随便找个不同的颜色
- 若当前点颜色和这条边颜色不同,则直接将其子节点的颜色定为这条边的颜色
不难发现这样总能找到一种保留生成树上所有边的染色方案
#include<cstdio>
#include<iostream>
#include<vector>
#include<utility>
#define RI register int
#define CI const int&
using namespace std;
typedef pair <int,int> pi;
const int N=100005;
int n,m,x,y,z,vis[N],col[N]; vector <pi> v[N],nv[N];
inline void DFS1(CI now=1)
{
vis[now]=1; for (auto [to,c]:v[now])
if (!vis[to]) nv[now].push_back(pi(to,c)),DFS1(to);
}
inline void DFS2(CI now=1,CI ban=0)
{
if (!col[now]) col[now]=ban%n+1;
for (auto [to,c]:nv[now])
if (c==col[now]) DFS2(to,c); else col[to]=c,DFS2(to,0);
}
int main()
{
RI i; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
scanf("%d%d%d",&x,&y,&z),v[x].push_back(pi(y,z)),v[y].push_back(pi(x,z));
for (DFS1(),col[1]=1,DFS2(),i=1;i<=n;++i) printf("%d\n",col[i]);
return 0;
}
AtCoder arc148_d mod M Game
挺有意思的一个博弈,想到关键的地方就不难了
不妨先倒着考虑,假设此时只剩下两个数\(x,y\),此时两个人的数之和分别为\(A,B\)
如果此时Bob能获胜,则必须同时满足:
\[A+x\equiv B+y\pmod M\\ A+y\equiv B+x\pmod M \]即\(2x\equiv 2y\pmod M\),我们不妨把满足这个等式的\(x,y\)称为配对
显然,两个相同的数总能配对;而另一种配对的情况则是当\(M\)为偶数时,\(|x-y|=\frac{M}{2}\)
不难发现当且仅当可以把\(2n\)个数全部两两配对时Bob才能获胜,\(M\)是奇数的情况很显然,而\(M\)是偶数的情况还需要加一个特判
不妨考虑以下数据
2 4
0 1 1 2
如果直接按照上面的结论,两个\(1\)配对,\(0\)和\(2\)配对会得出Bob获胜的结论,但实际上最后两个数之和差了\(\frac{M}{2}\)
不难发现,我们还需要统计出\(\ge \frac{M}{2}\)的数个数\(cnt\),当\(cnt\)为偶数时就不会出现上面那种情况了
#include<cstdio>
#include<iostream>
#include<map>
#define RI register int
#define CI const int&
using namespace std;
int n,m,x,cnt; map <int,int> rst;
int main()
{
RI i; for (scanf("%d%d",&n,&m),i=1;i<=2*n;++i)
{
scanf("%d",&x); if (m%2==0&&x>=m/2) x-=m/2,++cnt; ++rst[x];
}
if (cnt%2==1) return puts("Alice"),0;
for (auto [_,c]:rst) if (c%2==1) return puts("Alice"),0;
return puts("Bob"),0;
}
AtCoder - arc108_c AB
这题明明有\(\log n\)的做法,但出题人给\(n\le 1000\)的迷惑数据范围就很奇怪,不知道是不是有\(O(n^2)\)的直接DP做法
这题的核心就是手玩+分类讨论,只要把Case搞清楚做法其实都很简单,以\(c_{AB}=A\)的情况为例:
- 当\(c_{AA}=A\)时,此时不管怎么样都只能在中间加\(A\)
- 当\(c_{AA}=B\and c_{BA}=A\)时,此时开头的\(A\)和结尾的\(AB\)是定死的,而中间的\(n-3\)个位置可以任意放\(A,B\),但存在限制不能有两个相邻的\(B\)出现
- 当\(c_{AA}=B\and c_{BA}=B\)时,此时开头的\(A\)和结尾的\(AB\)是定死的,而中间的\(n-3\)个位置可以任意放\(A,B\)
直接手玩的话第三种情况可能会比较模糊,但实际上我们可以写个暴力打个表出来看下就一目了然了
第二种情况的方案数可以简单DP得出(当然很容易发现其实就是斐波那契数列),第三种情况的方案数就是\(2^{n-3}\)
注意特判\(n\le 3\)的情况
#include<cstdio>
#include<iostream>
#include<string>
#include<set>
#include<queue>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005,mod=1e9+7;
int n,f[N][2]; string AA,AB,BA,BB;
int main()
{
cin>>n>>AA>>AB>>BA>>BB;
if (n<=3) return puts("1"),0;
if ((AA=="A"&&AB=="A")||(BB=="B"&&AB=="B")) return puts("1"),0;
if ((AA=="B"&&AB=="A"&&BA=="A")||(BB=="A"&&AB=="B"&&BA=="B"))
{
f[1][0]=f[1][1]=1; for (RI i=2;i<=n-3;++i)
f[i][0]=(f[i-1][0]+f[i-1][1])%mod,f[i][1]=f[i-1][0];
return printf("%d",(f[n-3][0]+f[n-3][1])%mod),0;
}
int ans=1; for (RI i=1;i<=n-3;++i) ans=2LL*ans%mod;
return printf("%d",ans),0;
}
AtCoder - arc148_e ≥ K
经典Atcoder计数题,看到这题就知道我该下班了
排列计数的经典做法就是考虑插入,而一般为了便于统计我们会强制定下插入的顺序,这题的大致思路就是如此
考虑合法序列的形态,发现以下两个条件就是充要的:
- 不能出现两个\(<\frac{k}{2}\)的数相邻
- 对于两个相邻的数\(x,y\),若\(x<\frac{k}{2},y\ge \frac{k}{2}\)则\(|y-\frac{k}{2}|\ge |x-\frac{k}{2}|\)
考虑按照\(|a_i-\frac{k}{2}|\)从大到小插入,并把相同的数放在一起考虑,这样的好处就是保证不会出现第二种不合法情况
因此考虑限制第一种情况,设\(cur\)表示此时可以插入的位置数\(cur\),则有:
- 当\(x<\frac{k}{2}\)时,设其出现次数为\(y\),则插入方法有\(C_{cur}^y\)种,并且之后可用位置数\(cur\)减去\(y\)
- 当\(x\ge \frac{k}{2}\)时,设其出现次数为\(y\),此时插入的方法等价于,把\(y\)个数划分成\(cur\)份,并允许为空,利用插板法知道此时方案数为\(C_{cur+y-1}^{cur-1}\),并且之后可用位置数\(cur\)加上\(y\)
然后这题就做完了,复杂度\(O(n\log n)\)
#include<cstdio>
#include<iostream>
#include<vector>
#include<utility>
#include<map>
#include<algorithm>
#define RI register int
#define CI const int&
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=200005,mod=998244353;
int n,k,x,fact[N],ifac[N]; map <int,int> rst;
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
for (ifac[n]=quick_pow(fact[n]),i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
inline int C(CI n,CI m)
{
if (n<m||n<0||m<0) return 0;
return 1LL*fact[n]*ifac[m]%mod*ifac[n-m]%mod;
}
int main()
{
RI i; for (scanf("%d%d",&n,&k),i=1;i<=n;++i) scanf("%d",&x),++rst[x];
vector <pi> vec; for (auto it:rst) vec.push_back(it);
auto cmp=[&](const pi& A,const pi& B)
{
return abs(2*A.fi-k)!=abs(2*B.fi-k)?abs(2*A.fi-k)>abs(2*B.fi-k):A.fi>B.fi;
};
sort(vec.begin(),vec.end(),cmp); init(n);
int ans=1,cur=1; for (auto [val,num]:vec)
if (val*2<k) ans=1LL*ans*C(cur,num)%mod,cur-=num;
else ans=1LL*ans*C(cur+num-1,cur-1)%mod,cur+=num;
return printf("%d",ans),0;
}
AtCoder - arc108_f Paint Tree
这题比赛的时候大家都会而我只能干瞪眼,只能说和Counting没有什么相性
这题的核心就是要想到利用直径,不妨先找出原树的一条直径,记其长度为\(d\),端点为\(x,y\)
显然若\(x,y\)颜色相同则贡献为\(d\),方案数为\(2\times 2^{n-2}=2^{n-1}\),接下来考虑这两点颜色不同的情况
不妨尝试枚举答案\(k\),那么所有到\(x\)距离\(>k\)的点颜色必须和\(y\)一样x,所有到\(y\)距离\(>k\)的点颜色必须和\(x\)一样
而如果某个点到\(x,y\)的距离都\(\le k\),那么这个点的颜色就可以随便取,因为根据树的直径的性质,这个点到任何一个点的距离都\(\le k\)
很容易由此观察出一个容斥的做法,不妨设\(f(k)\)表示贡献\(\le k\)的树的方案数,显然用\(f(k)-f(k-1)\)即可得出贡献为\(k\)的方案数了
根据上面所说的,我们设\(cnt_k\)表示到\(x,y\)的距离均\(\le k\)的点的个数,则\(f(k)=2^{cnt_k}\),就可以轻松计算答案了
#include<cstdio>
#include<iostream>
#include<vector>
#define RI register int
#define CI const int&
using namespace std;
const int N=200005,mod=1e9+7;
int n,x,y,st,dis1[N],dis2[N],bkt[N],pw[N],ans; vector <int> v[N];
inline void DFS(CI now,int* dis,CI fa=0)
{
for (auto to:v[now]) if (to!=fa) dis[to]=dis[now]+1,DFS(to,dis,now);
}
int main()
{
RI i; for (scanf("%d",&n),i=1;i<n;++i)
scanf("%d%d",&x,&y),v[x].push_back(y),v[y].push_back(x);
for (pw[0]=i=1;i<=n;++i) pw[i]=2LL*pw[i-1]%mod;
for (DFS(1,dis1),x=i=1;i<=n;++i) if (dis1[i]>dis1[x]) x=i;
for (dis1[x]=0,DFS(x,dis1),y=i=1;i<=n;++i) if (dis1[i]>dis1[y]) y=i;
DFS(y,dis2); for (i=1;i<=n;++i) if (i!=x&&i!=y)
st=max(st,min(dis1[i],dis2[i])),++bkt[max(dis1[i],dis2[i])];
for (i=1;i<=n;++i) bkt[i]+=bkt[i-1];
for (i=st;i<=dis1[y];++i)
(ans+=1LL*i*(pw[bkt[i]]-(i>st?pw[bkt[i-1]]:0)+mod)%mod)%=mod;
return printf("%d",(2LL*ans+1LL*dis1[y]*pw[n-1]%mod)%mod),0;
}
Postscript
这场剩下J题整场没人尝试就拉倒了,而K这个造计算机题被徐神干了一整场干过去了,那我就不管了
你们有没有这样的徐神啊,真是徐徐又神神啊
标签:CI,const,int,Day4,UESTC,2024,include,RI,define From: https://www.cnblogs.com/cjjsb/p/18024009