CF1458E
先不考虑特殊点，考虑把两堆石子的状态看成坐标轴上的点，那么每一行每一列只有一个非法状态，考虑把所有非法状态处理出来，用意发现这是一条 (45) 度的斜线。考虑它碰到了一个特殊点，假设这个特殊点在他左边，也就是说它从下面撞上了这个特殊点引出来的线平行于 x 轴的那一条，这相当于对其做了次向上偏移。我们考虑维护这个折线，有一种很好的写法是把截距相同的一段直接记在map里。具体实现可以参考代码（我也是参考别人的）
#include <bits/stdc++.h>
using namespace std;
const int inf=1e9;
const int MAXN=100005;
template <typename T>
void read(T &x) {
T flag=1;
char ch=getchar();
for (; '0'>ch||ch>'9'; ch=getchar()) if (ch=='-') flag=-1;
for (x=0; '0'<=ch&&ch<='9'; ch=getchar()) x=x*10+ch-'0';
x*=flag;
}
struct node{
int x, y;
}p[MAXN];
int n, m;
map<int, int> mnx, mny;
map<pair<int, int>, bool> mark;
map<int, map<int, int> > mp;
int main() {
read(n); read(m);
for (int i=1, x, y; i<=n; i++) {
read(x); read(y);
mark[make_pair(x, y)]=true;
if (mnx.find(x)==mnx.end()) mnx[x]=y;
else mnx[x]=min(mnx[x], y);
if (mny.find(y)==mny.end()) mny[y]=x;
else mny[y]=min(mny[y], x);
}
int nowx=0, nowy=0;
for (; nowx<=inf&&nowy<=inf; ) {
if (mnx.find(nowx)!=mnx.end()&&mnx[nowx]<=nowy) {
nowx++;
continue;
}
if (mny.find(nowy)!=mny.end()&&mny[nowy]<=nowx) {
nowy++;
continue;
}
if (mnx.find(nowx)!=mnx.end()||mny.find(nowy)!=mny.end()) {
mark[make_pair(nowx, nowy)]=true;
nowx++;
nowy++;
continue;
}
map<int, int> :: iterator x=mnx.lower_bound(nowx), y=mny.lower_bound(nowy);
int tmp=inf;
if (x!=mnx.end()) tmp=min(tmp, (*x).first-nowx);
if (y!=mny.end()) tmp=min(tmp, (*y).first-nowy);
mark[make_pair(nowx, nowy)]=true;
mp[nowx-nowy][nowx+tmp]=nowx;
nowx+=tmp;
nowy+=tmp;
}
for (int i=1; i<=m; i++) {
int a, b;
read(a); read(b);
if (mark[make_pair(a, b)]) puts("LOSE");
else {
map<int, int> :: iterator it=mp[a-b].upper_bound(a);
if (it!=mp[a-b].end()&&(*it).second<=a) {
puts("LOSE");
} else {
puts("WIN");
}
}
}
return 0;
}//kel
CF1147F
这道题有一个关键是第一步不需要考虑前面的限制，那么我们猜想先手（B）不知道怎么输。考虑任意取出一组最大匹配中的两条匹配边 ((u,v),(p,q))，不妨设先手选择的是 Increasing，那么对于 (w(v,p)>w(u,v)) 有 (w(p,q)<w(v,p)) 那么这组匹配被称作好的。对于一组好的匹配，我们发现后手只要走匹配边即可。下面证明一定存在好的匹配，我们只需找出这组好的匹配即可。如果 (exists w(u,v)<w(v,p)<w(p,q))，我们将这组匹配改为 ((p,v),(u,q)) 即可变成一组好的，容易发现这就是我们在做稳定婚姻问题是更改匹配边的过程，所以我们对左侧点定义满意度为从小到大，右侧点为从大到小跑稳定婚姻问题即可。
#include <bits/stdc++.h>
#define pii std::pair<int,int>
#define mp std::make_pair
#define F first
#define S second
const int maxn=105;
template<typename T>
void read(T &x){
T flag=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')flag=-1;
for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0';
x*=flag;
}
int n,a[maxn][maxn],rnk[maxn][maxn],pos[maxn],nxt[maxn],p;
std::priority_queue<pii>pq;
std::queue<int>q;
void solve(){
read(n);
for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)read(a[i][j]);
putchar('B');putchar('
');
fflush(stdout);
char ch;scanf("%c",&ch);
if(ch=='D')for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=-a[i][j];
read(p);
if(p>n)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=-a[i][j];
for(int i=1;i<=n;i++){
q.push(i);
for(int j=1;j<=n;j++)pq.push(mp(-a[i][j],j+n));
int tmp=0;
while(!pq.empty()){
int u=pq.top().S;pq.pop();
rnk[i][++tmp]=u;
}
}
for(int i=1;i<=n+n;i++)nxt[i]=0;
while(!q.empty()){
int u=q.front();q.pop();
if(!u)continue;
for(int i=1;i<=n&&!nxt[u];i++){
int w=rnk[u][i];
if(!nxt[w]||a[u][w-n]>a[nxt[w]][w-n])nxt[nxt[w]]=0,q.push(nxt[w]),nxt[u]=w,nxt[w]=u;
}
}
while(1){
if(p==-1||p==-2)break;
printf("%d
",nxt[p]);fflush(stdout);
read(p);
}
}
int main(){
int T;scanf("%d",&T);
while(T--)solve();
return 0;
}
CF1033
这道题得发现一个看起来很套路但又不太敢相信它是对的的套路。设当前局面为 (S)，定义 (S') 为每个 (v' o v mod (a+b)) 后的局面，则 (S) 和 (S') 的赢家是同样的人。
证明咕。
然后考虑计数，当 A 或 B 必胜时只与 ((a,b)) 有关，所以令 (a'=b,b'=a) 那么胜负关系就反转了，所以 A 胜的方案一定与 B 胜的方案相同，所以我们只需要求出先手胜和后手胜的方案。注意每个 (v'_i<a+b)。
#include<bits/stdc++.h>
#define pb push_back
#define mp std::make_pair
#define pii std::pair<int,int>
#define F first
#define S second
typedef long long ll;
typedef unsigned long long ull;
namespace _name{
const int maxn=105,mod=998244353,inf=0x3f3f3f3f;
template<typename T>
inline void read(T &x){
T flag=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')flag=-1;
for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0';
x*=flag;
}
template<typename T>
inline void write(T x){
if(x==0)return putchar('0'),void();
int stk[20],top=0;
while(x)stk[++top]=x%10,x/=10;
for(int i=top;i;i--)putchar(stk[i]+'0');
}
template<typename T>
inline void print(T x,char End='
'){
if(x<0)x=-x,putchar('-');
write(x);putchar(End);
}
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(int a,int b){return a-b<0?a-b+mod:a-b;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline int ksm(int a,int b=mod-2){int ret=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;}
}using namespace _name;
int n;
ll m,v[maxn],w[maxn],ans[2];
int main(){
read(n);read(m);for(int i=1;i<=n;i++)read(v[i]);
for(int s=2;s<=2*m;s++){
for(int i=1;i<=n;i++)w[i]=v[i]%s;
std::sort(w+1,w+1+n,[](const int a,const int b){return a>b;});
w[0]=s-1;
for(int i=0,id=0;i<=n;i++,id^=1){
int l=std::max(w[i+1],w[id+1]/2)+1,r=std::min(m,w[i]);
ans[id]+=std::max(0,std::min(r,s-l)-std::max(l,s-r)+1);
}
}
print((1ll*m*m-ans[0]-ans[1])/2,' ');print((1ll*m*m-ans[0]-ans[1])/2,' ');print(ans[1],' ');print(ans[0]);
return 0;
}
AGC010D
如果存在一个 (1) 那么只用看其他数的和的奇偶性。否则如果没有偶数那么后手只要模仿先手即可，先手必败。所以如果只有一个偶数那么先手必胜。如果有奇数个偶数，注意到不可能全是偶数（因为一开始的 (gcd) 是 (1)），那么先手可以保证一直都是奇数个偶数，最后一定会变成 (1) 个偶数，先手必胜。考虑偶数的偶数，因为先手想赢，他只有一种办法，那就是只有一个奇数，然后给这个奇数-1，剩下全除以 (gcd)，这种情况直接递归去做即可。
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100005], cnt;
long long sum;
int ans;
void work(int id) {
sum=0;
cnt=0;
for (int i=1; i<=n; i++) {
if (a[i]==1) {
for (int j=1; j<=n; j++) sum+=a[j]-1;
if(sum&1) ans=id;
else ans=1-id;
return;
}
if(!(a[i]&1)) cnt++;
}
if (cnt&1) ans=id;
else {
if (n-cnt>1) ans=1-id;
else {
int g=0;
for (int i=1; i<=n; i++) if (a[i]&1) a[i]--;
for (int i=1; i<=n; i++) g=__gcd(g, a[i]);
for (int i=1; i<=n; i++) a[i]/=g;
work(1-id);
}
}
}
int main() {
scanf("%d", &n);
for (int i=1; i<=n; i++) scanf("%d", a+i);
work(1);
if (ans) puts("First");
else puts("Second");
return 0;
}
AGC026F
对于 (n) 为偶数的情况，通过反证法可以得知一定选左右开始。
对于奇数情况，由上可知一定选一个偶数的位置，然后后手会得到主动权然后递归去做，最后先手选了奇数的一段
考虑先全部选偶数，然后把一段改为奇数，这可以通过前缀和 (+s[r]-s[l-1]) 实现。
直接二分答案，然后求出合法区间，要求这些合法区间必须首位相连，即 (r_{i}+1=l_{i+1}-1)
我们可以使用一个 dp 判断，设 (dp_{i}) 代表 [1,i] 有没有合法区间划分，我们只需找到一个 (dp_{j}=1) 且 (s[i-1]-s[j]>=mid)
然后发现可以优化直接取最小的 (s[j]) 即可，复杂度 (O(nlog{n}))
#include <bits/stdc++.h>
#define pii std::pair<int,int>
#define mp std::make_pair
#define F first
#define S second
const int maxn=300005;
template<typename T>
void read(T &x){
T flag=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')flag=-1;
for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0';
x*=flag;
}
int n,w[maxn],s[maxn],zz[2];
bool check(int m){
int mn=0;//dp[0]
for(int i=2;i<=n;i+=2)if(s[i-1]-mn>=m)mn=std::min(mn,s[i]);
return s[n]-mn>=m;
}
int main(){
read(n);for(int i=1;i<=n;i++)read(w[i]),zz[i&1]+=w[i];
if(!(n&1)){
printf("%d %d
",std::max(zz[0],zz[1]),std::min(zz[0],zz[1]));
}else{
for(int i=1;i<=n;i++)s[i]=s[i-1]+(i&1?w[i]:-w[i]);
int l=0,r=zz[0]+zz[1],res=0;
while(l<=r){
int mid=(l+r)>>1;
if(check(mid))l=mid+1,res=mid;
else r=mid-1;
}
printf("%d %d
",zz[0]+res,zz[1]-res);
}
return 0;
}