Preface
打的就是依托答辩,当时看一眼D感觉是个爆搜不想写就先跳了去想F,结果傻逼了没想出来
最后30min了赶紧溜回去把D爆搜写了,但是已经罚时爆炸了,其实如果正常正序做的话排名会挺稳的
后面一问包大爷发现F是个傻逼题,只能说计数水平实在是低下
A - Order Something Else
签到题
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#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=1005;
int t,n,a[N],P,Q,mi=1e9;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d%d%d",&n,&P,&Q),i=1;i<=n;++i)
scanf("%d",&a[i]),mi=min(mi,a[i]);
return printf("%d",min(P,Q+mi)),0;
}
B - Strictly Superior
签到题,重在阅读题意
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#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=105;
int t,n,m,p[N],c[N],x,f[N][N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j,k; for (scanf("%d%d",&n,&m),i=1;i<=n;++i)
{
for (scanf("%d%d",&p[i],&c[i]),j=1;j<=c[i];++j)
scanf("%d",&x),f[i][x]=1;
}
for (i=1;i<=n;++i) for (j=1;j<=n;++j) if (i!=j)
{
if (p[i]<p[j]) continue;
bool flag=1; for (k=1;k<=m;++k)
if (f[i][k]&&!f[j][k]) { flag=0; break; }
if (!flag) continue;
if (p[i]>p[j]||c[i]<c[j]) return puts("Yes"),0;
}
return puts("No"),0;
}
C - Reversible
以后我再写自然溢出的Hash我就是傻逼好吧
Hash被卡了一发后有点急了就直接Rush了棵字典树上去,后面发现可以直接用set <string>
艹过去
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=200005;
int n,m,ans; char s[N],t[N];
class Trie
{
private:
int ch[N][26],tot; bool ed[N];
public:
inline void insert(char *s,CI n)
{
int now=0; for (RI i=1;i<=n;++i)
{
if (!ch[now][s[i]-'a']) ch[now][s[i]-'a']=++tot;
now=ch[now][s[i]-'a'];
}
ed[now]=1;
}
inline bool find(char *s,CI n)
{
int now=0; for (RI i=1;i<=n;++i)
{
if (!ch[now][s[i]-'a']) return 0;
now=ch[now][s[i]-'a'];
}
return ed[now];
}
}T;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)
{
scanf("%s",s+1); m=strlen(s+1); for (j=1;j<=m;++j) t[j]=s[m-j+1];
int flag=0; for (j=1;j<=m;++j) if (s[j]!=t[j]) { flag=s[j]<t[j]; break; }
if (flag==0) for (j=1;j<=m;++j) s[j]=t[j];
if (!T.find(s,m)) T.insert(s,m),++ans;
}
return printf("%d",ans),0;
}
D - Peaceful Teams
感觉还是要一定技巧的爆搜题,如果纯搜的话可能会T(据包大爷所说)
不妨设\((now,num)\)表示当前搜索到第\(now\)个点,已经划分了\(num\)个组
考虑大力枚举这个数在前面的哪一组里,顺带维护下每个组的限制关系
当然还有一种操作就是新增一个组,这个也很好处理
这种写法的一个好处就是限制了每个组中最小的元素的标号递增,因此比起纯爆搜要少一个最后除以排列数的东西,因此跑的飞快
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=15,mod=998244353;
int n,t,m,x,y,ans,vis[N],f[N][N],c[N]; vector <int> v[N];
inline void DFS(CI now,CI num)
{
if (num>t) return;
if (now>n) return (void)(ans+=num==t);
for (RI i=1;i<=num;++i)
if (!f[i][now])
{
c[now]=i; for (int to:v[now]) ++f[i][to];
DFS(now+1,num); for (int to:v[now]) --f[i][to];
}
c[now]=num+1; for (int to:v[now]) ++f[num+1][to];
DFS(now+1,num+1); for (int to:v[now]) --f[num+1][to];
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d%d%d",&n,&t,&m),i=1;i<=m;++i)
scanf("%d%d",&x,&y),v[x].push_back(y);
return DFS(1,0),printf("%d",ans),0;
}
E - NAND repeatedly
考虑把所有右端点为\(i\)的区间一起考虑,设\(x_i\)表示这些区间中值为\(0\)的区间个数,\(y_i\)表示值为\(1\)的区间个数
根据新加入的一个点的权值可以很容易的写出递推关系,就很容易维护答案了
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef unsigned long long u64;
typedef pair <int,int> pi;
const int N=1000005;
int n,x[N],y[N]; char s[N]; long long ans;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d%s",&n,s+1),i=1;i<=n;++i)
{
if (s[i]=='1') x[i]=y[i-1],y[i]=x[i-1],++y[i];
else x[i]=1,y[i]=x[i-1]+y[i-1]; ans+=y[i];
}
return printf("%lld",ans),0;
}
F - Make 10 Again
其实很trivial的一道题,但想的思路可能有点问题,应该看到\(10\)第一反应就是状压的
由于这里有一个任取的要求,所有朴素的DP都不太好维护状态,不过由于要求的范围很小,所以考虑状压
设\(f_{i,S}\)表示处理了前\(i\)个骰子,其中能表示的数的状态为\(S\)的概率,不难发现\(S\)只要存储\(\le 10\)的信息即可,多余的部分没有意义
那么我们转移的时候先把\(\min(10,a_i)\)的数的选法转移了,然后考虑若\(a_i>10\),只要把数组的值原封不动地乘上\(\frac{a_i-10}{a_i}\)即可
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair <int,int> pi;
const int N=105,M=1<<11,mod=998244353;
int n,a[N],f[N][M],ans;
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 inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j,k; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
for (f[0][1]=i=1;i<=n;++i)
{
int div=quick_pow(a[i]);
for (j=0;j<M;++j) for (k=1;k<=min(10,a[i]);++k)
inc(f[i][j|((j<<k)&(M-1))],1LL*f[i-1][j]*div%mod);
if (a[i]>10) for (j=0;j<M;++j)
inc(f[i][j],1LL*f[i-1][j]*(a[i]-10)%mod*div%mod);
}
for (i=0;i<M;++i) if ((i>>10)&1) inc(ans,f[n][i]);
return printf("%d",ans),0;
}
G - Takahashi And Pass-The-Ball Game
考虑先把传球的过程做一遍,然后接下来考虑求出再做了\([0,K-1]\)遍的情况,全部累计后最后除以\(K\)即可
然后这题有一个关键的性质,就是大的操作可以拆分为若干个小的操作,而操作次数多的贡献可以向前累计到次数小的地方
直接讲有点抽象,可以看下下面这个Tutorial里的图片理解下:
因此考虑倍增求解,先预处理出\(go_{i,j}\)表示从\(i\)开始向后跳\(j\)次到达的位置,这样我们可以先把球放在对应的次数上,然后向前累计即可
具体实现可以看代码,复杂度\(O(n\log K)\)
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<unordered_set>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair <int,int> pi;
const int N=200005,mod=998244353;
int n,a[N],b[N],go[N][60],f[N][60],ans[N]; long long k;
inline void inc(int& x,CI y)
{
if ((x+=y)>=mod) x-=mod;
}
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;
}
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (scanf("%d%lld",&n,&k),i=1;i<=n;++i)
scanf("%d",&a[i]),go[i][0]=a[i];
for (i=1;i<=n;++i) scanf("%d",&b[i]);
for (j=1;j<60;++j) for (i=1;i<=n;++i) go[i][j]=go[go[i][j-1]][j-1];
for (i=1;i<=n;++i)
{
int x=i; for (j=0;j<60;++j) if ((k>>j)&1)
inc(f[x][j],b[i]),x=go[x][j];
}
for (j=59;j>=0;--j) for (i=1;i<=n;++i)
inc(f[i][j-1],f[i][j]),inc(f[go[i][j-1]][j-1],f[i][j]);
for (i=1;i<=n;++i) inc(ans[a[i]],f[i][0]);
int inv=quick_pow(k%mod);
for (i=1;i<=n;++i) printf("%d ",1LL*ans[i]*inv%mod);
return 0;
}
Postscript
寄寄寄寄,摆摆摆摆摆
- Contest Programming Beginner AtCoder freeecontest programming beginner atcoder contest programming securities beginner contest programming beginner registry contest programming beginner keyence contest programming beginner systems beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332