[CF 925](Dashboard - Codeforces Round 925 (Div. 3) - Codeforces)

补题ing 待更新

后面打算更新D题和power oj上一道区间合并的题（现在才知道是一道洛谷上的原题……）

[E](Problem - E - Codeforces)

分析

手写的模拟过程

​ 博弈论加贪心，实际上后手得到的答案只看其位数是否大于m，先手的倒置是把后缀0的个数从位数减去，而后手可以通过合并使后缀0不存在，所以对先手而言，只消每轮删去后缀0个数最多的，而后手同样选一个后缀0最多的跟一个没有后缀0的合并(因为先手操作过，这种数一定存在)，使其没有后缀0，这样它被倒置也不会减少位数，也就是这样可以使后手得到的位数员供献最少，这也是后手的最佳方案

比如5550 20 300
先手的操作一定是300先，这样对他收益大，5550和20的只能操作一个，但对后手没有影响，因为它们后缀0个数一样。

操作

​ 所以可以把数遍历一下，统计位数还有后缀0个数，按后缀0个数从大到小排，奇数位上的都被先手操作过，所以最后后手得到的数的位数就是初始位数-奇数位后缀0个数，再用这个跟m比较，严格大于才是后手胜，否则是先手胜。

如 1 2007 800 1580

排序后为 800 1580 2007 1 (后两个可颠倒顺序)

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
const int N=2e5+5;
int a[N],b[N];//b数组统计后缀0个数
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
	int t,n,m,x,y;cin>>t;
	while(t--){
		cin>>n>>m;
		int cnt=0;//统计位数
		for(int i=1;i<=n;i++){
			cin>>a[i];
			b[i]=0;
		}
		for(int i=1;i<=n;i++){
            //注意两个while的顺序
			while(a[i]%10==0){
				a[i]/=10;
				b[i]++;
				cnt++;
			}
			while(a[i]){
				a[i]/=10;
				cnt++;
			}
		}
		sort(b+1,b+n+1,[](int a,int b){
			return a>b;
		});
		for(int i=1;i<=n;i+=2){
			cnt-=b[i];//先手总操作奇数位
		}
		if(cnt>m) cout<<"Sasha";
		else cout<<"Anna";
		cout<<endl;

	}
	return 0;
}

[F](Problem - F - Codeforces)

分析

​ 每个参与者都把自己排在最前面，因此我们找相对顺序时可以不管第一个。

1 2 3 4		2<-3<-4
2 3 1 4		3<-1<-4
3 2 1 4		2<-1<-4
4 2 3 1		2<-3<-1

由此可构造拓扑序

操作

​ 对k个顺序的第2到n个依次建边，求拓扑序是否存在，即是否满足cnt=n

代码

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define db(x) cout<<x<<" "<<endl;
#define _db(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" ";cout<<endl;
#define mem(a) memset(a,0, sizeof(a))
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define per(i,r,l) for(int i=r;i>=l;i--)
const int N=2e5+5;
int a[N],rd[N],n,cnt;
vector<int>e[N];
bool tuopu(){
    //这里可以就用普通队列
	priority_queue<int,vector<int>,greater<int>>q;
	cnt=0;
	for(int i=1;i<=n;i++){
		if(rd[i]==0) q.push(i);
	}
	while(!q.empty()){
		int x=q.top();
		q.pop();
		for(auto t:e[x]){
			rd[t]--;
			if(rd[t]==0) q.push(t);
		}
		cnt++;
	}
	return cnt==n;
}
signed main()
{
std::ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
	int t,x,k,ans=0;cin>>t;
	while(t--){
		cin>>n>>k;
		//注意用memset初始化会t 
		for(int i=1;i<=n;i++){
			e[i].clear();
			rd[i]=0;
		}
		while(k--){
			for(int i=1;i<=n;i++){
				cin>>a[i];
				if(i>=3){
					e[a[i]].push_back(a[i-1]);
					rd[a[i-1]]++;
				}
			}
			
		}
		if(tuopu()){
			cout<<"YES";
		}
		else cout<<"NO";
		cout<<endl;
	}
	return 0;
}