Preface
AGC好难啊,这场补完最近就没啥比赛好补了,接下来去训练下专题吧
像C题这种美妙的人类智慧题感觉以我的脑子一辈子也想不出来www
A - Mex Game
对于任意一段前缀,我们可以求出对应的每个人的操作次数以及每个人拥有的位置数
考虑Alice的最优策略一定是从小到大地放入Bob对应的格子所对的下标,Bob同理
因此只要检验一下谁的格子还有剩余即可
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int n,CA,CB; char s[N];
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; if (scanf("%d%s",&n,s+1),s[1]=='A') ++CA; else ++CB;
for (i=2;i<=n+1;++i)
{
if (s[i]=='A') ++CA; else ++CB;
int OA=i/2,OB=(i-1)/2;
puts(CA-OB>0?"Alice":"Bob");
}
return 0;
}
B - Insert 1, 2, 3, ...
刚开始想假了写了个线段树上二分,后面发现就是个傻逼题
首先考虑当左端点确定时,合法的右端点的取值一定是连续的一段,这就提示我们考虑如何对于每个左端点快速求出右端点
手玩一下会发现如果我们把所有无法被表示的下标扔到一个栈里,只要每次看一下能否在这次操作中把栈顶元素表示掉即可
总复杂度\(O(n)\),具体实现看代码
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=500005;
int n,a[N],stk[N],top; LL ans;
int main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
for (stk[top=1]=n+1,a[n+1]=-1,i=n;i>=1;--i)
{
stk[++top]=i; int lst=1;
while (a[stk[top]]==lst) --top,++lst;
ans+=stk[top]-i;
}
return printf("%lld",ans),0;
}
C - Add Mod Operations
人类智慧题,完全想不到的说
首先把无解的情况判掉,显然当出现\(\exist i,j\in[1,n],a_i=a_j\and b_i\ne b_j\)这种情况就一定不合法,否则均可以构造解
然后我们可以对\(a_i\)升序排序,考虑如果每次操作\(y=\max(a)+x\),那么总可以把序列中最大的元素变成\(0\)并将其它元素加上\(x\)
考虑先依照此法操作\(n\)次,这样我们得到的序列形如:\(0,x_n,x_n+x_{n-1},\cdots,\sum_{i=3}^n x_i,\sum_{i=2}^n x_i\)
不难发现相邻两项间的差值总是正的,那么如果\(b\)满足单调不降且\(b_1=0\)那么就可以确定一组\(\{x_n\}\)
但如果不满足的话我们也有方法,不妨搞一个很大的数\(\infty\),然后令\(b'_i=b_i+(i-1)\times \infty\),这样\(\{b'\}\)就是单调不降的
我们只需要在最后一次操作做一遍\(x_{n+1}=b_1,y_{n+1}=\infty\)即可
但题目要求的是操作次数要\(\le n\),这样就得考虑怎么样可以省下一次操作,不难发现其实最后操作\(n\)次的序列中并没有\(x_1\),这就提醒我们从这里入手
考虑把原来操作的\(x_1\)修改为\(x_1-a_1\),这样在操作\(n-1\)次后的序列就形如:\(\sum_{i=1}^{n-1} x_i,0,x_{n-1},\cdots,\sum_{i=3}^{n-1} x_i,\sum_{i=2}^{n-1} x_i\)
不妨修改\(b'_1=b_1+(n-1)\times \infty,b'_i=b_i+(i-1)\times \infty (i\in[2,n])\),这样最后一次操作\(x_n=b_2,y_n=\infty\)即可
实现中取\(\infty =2\times 10^9+1\)即可
#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define int long long
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=1005,INF=2e9+1;
int n,a[N],b[N],x[N],y[N]; pi d[N];
inline void work(CI x,CI y)
{
for (RI i=1;i<=n;++i) a[i]=(a[i]+x)%y;
}
signed main()
{
//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
RI i,j; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]);
for (i=1;i<=n;++i) scanf("%lld",&b[i]),d[i]=pi(a[i],b[i]);
for (i=1;i<=n;++i) for (j=i+1;j<=n;++j)
if (a[i]==a[j]&&b[i]!=b[j]) return puts("No"),0;
sort(d+1,d+n+1); n=unique(d+1,d+n+1)-d-1;
for (i=1;i<=n;++i) a[i]=d[i].fi,b[i]=d[i].se;
if (n==1) return printf("Yes\n1\n%lld %lld\n",(b[1]-a[1]+INF)%INF,INF),0;
x[1]=b[1]-b[n]+INF-a[1]; x[n]=b[2]; y[n]=INF;
for (i=2;i<=n-1;++i) x[i]=b[n-i+2]-b[n-i+1]+INF;
for (i=1;i<=n-1;++i) y[i]=a[n-i+1]+x[i],work(x[i],y[i]);
for (printf("Yes\n%lld\n",n),i=1;i<=n;++i) printf("%lld %lld\n",x[i],y[i]);
return 0;
}
Postscript
感觉以后AGC先放放不补了,以我现在的水平AGC的妙处都体会不太到,后面的题目是一点做不了
- AtCoder Contest Grand 063atcoder contest grand 063 authentic atcoder contest grand negative atcoder contest grand atcoder contest radius grand atcoder contest grand 022 atcoder contest grand 001 histogram atcoder contest grand atcoder contest grand 019 atcoder contest grand 017 atcoder contest grand 039