Codeforces Round #647 (Div. 1) 题解 (AB)

https://codeforces.com/contest/1361

A. Johnny and Contribution

题面看不懂系列

给定一个无向图，要求给所有点标上号(topic number)并且规则是，对于选中的那个点，它的标号为没在邻居的标号中出现的最小正整数（忽略暂时没标号的邻居）。问最终能不能让每个点的标号依次为 \(t_1,t_2,...,t_n\)，能的话要给出标号顺序

贪心贪心贪心，每个点按照 \(t\) 值从小到大进行操作即可

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
const int N=500010; typedef long long ll; const int inf=~0u>>2; 
vector<int> a[N];
struct node{int t,p;}w[N];
int lab[N];
int n,m;
vector<int> v;
int mex(int x){ //返回邻居中没有出现过的最小的正整数
	v.clear();
	for(auto p:a[x])
	if(lab[p])
		v.push_back(lab[p]);
	sort(v.begin(),v.end());
	unique(v.begin(),v.end());
	repeat(i,0,v.size())
	if(v[i]!=i+1)
		return i+1;
	return v.size()+1;
}
signed main(){
	cin>>n>>m;
	while(m--){
		int x,y; cin>>x>>y;
		a[x].push_back(y);
		a[y].push_back(x);
	}
	repeat(i,0,n){
		cin>>w[i].t;
		w[i].p=i+1;
	}
	sort(w,w+n,[](node a,node b){return a.t<b.t;});
	repeat(i,0,n){
		int t=mex(w[i].p);
		if(t!=w[i].t)
			cout<<-1<<endl,exit(0);
		lab[w[i].p]=w[i].t;
	}
	repeat(i,0,n)cout<<w[i].p<<‘ ‘;
	return 0;
}

B. Johnny and His Hobbies

这波啊，这波是贪心贪心贪心qwqqqqq

第一步排除 \(p=1\) 的情况（直接输出 \(n\%2\)）

从大到小遍历 \(p^{k_i}\)，对于某个 \(p^{k_i}\)，如果 \(difference\) 大于0就减去 \(p^{k_i}\)，否则加上。这么搞就是最优解辣

• 当然 \(difference\) 这么大肯定是不能直接算的。方法可能不唯一，我就介绍我的思路。由于 \(difference\) 可以被好多 \(p\) 整除，我们把 \(difference\) 写成 \(a\cdot p^b\) 的形式（其中 \(b\) 等于当前访问的 \(k_i\)）。然后我们发现，如果 \(a\) 大于1e6，或者小于 -1e6，那么后续的操作都不可能使 \(a\) 从正变零，或者从负变零。所以 \(a\) 大于 1e6 就把它赋值为 1e6，小于 -1e6 就赋值为 -1e6 就行了，这波操作可以防止 \(a\) 超 long long 范围
• 至于为什么是贪心呢，因为在贪心的过程中，不可能出现加/减一个数导致 \(difference\) 符号改变的情况（必须经过0），所以贪，就硬贪

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
#define fi first
#define se second
int cansel_sync=(ios::sync_with_stdio(0),cin.tie(0),0);
typedef long long ll;
#define int ll
const int N=1000010; const int inf=~0u>>2; 
const int mod=(1?1000000007:998244353); ll mul(ll a,ll b,ll m=mod){return a*b%m;} ll qpow(ll a,ll b,ll m=mod){ll ans=1; for(;b;a=mul(a,a,m),b>>=1)if(b&1)ans=mul(ans,a,m); return ans;} ll getinv(ll v,ll m=mod){return qpow(v,m-2,m);}
int a[N];
int T,n,p;
int ans,dif,nowpos; //dif是题解里的a，nowpos就是题解里的b
void move_to(int x){ //一波操作使nowpos变成x
	(ans*=qpow(p,nowpos-x))%=mod;
	if(dif){
		repeat(i,0,nowpos-x){
			dif=max(min(dif*p,N),-N);
			if(abs(dif)==N)break;
		}
	}
	nowpos=x;
}
void push(int x){ //处理p^x这个数，更新答案
	move_to(x);
	if(dif>0)ans--,dif--;
	else ans++,dif++;
}
signed main(){
	cin>>T;
	while(T--){
		cin>>n>>p;
		repeat(i,0,n)
			cin>>a[i];
		if(p==1){cout<<n%2<<endl; continue;}
		sort(a,a+n,greater<int>());
		ans=dif=0; nowpos=N;
		repeat(i,0,n)
			push(a[i]);
		move_to(0);
		cout<<(ans%mod+mod)%mod<<endl;
	}
	return 0;
}

Codeforces Round #647 (Div. 1) 题解 (AB)

原文：https://www.cnblogs.com/axiomofchoice/p/13049766.html