---

title : 第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（济南）
date : 2022-5-30
tags : ACM,题解，练习记录
author : Linno

---

第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（济南）

题目链接：https://ac.nowcoder.com/acm/contest/10662

补题进度：7/13 （ A C D G J L M ）

A-Matrix Equation

用线代知识对式子进行化简，发现我们最后要求的就是2^自由元个数。

高斯消元求秩然后快速幂做完了，队友写的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll qpow(ll a,ll b) {
    
	ll ans=1;
	while(b) {
    
		if(b&1)
			ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
const int N=205;
bitset<N>a[N];
bitset<N>b[N];
bitset<N>aa[N];
long long n;
int Gauss() {
    
	int r , c , cnt = 0;
	for (r = c = 1 ; r <= n && c <= n ; r++ , c++) {
    
		int p = 0;
		for (int j = r ; j <= n ; j++) {
    
			if (a[j][c]) {
    
				p = j;
				break;
			}
		}
		if (!p) {
    
			r--;
			cnt++;
			continue;
		}
		swap(a[r] , a[p]);
		for (int j = 1 ; j <= n ; j++) {
    
			if (j == r) continue;
			if (a[j][c] == 0) continue;
			a[j] ^= a[r];
		}
	}
	return n-cnt;
}
int main() {
    
	scanf("%lld",&n);
	int x;
	for(int i=1; i<=n; ++i) {
    
		for(int j=1; j<=n; ++j) {
    
			scanf("%d",&x);
			aa[i][j]=x;
		}
	}
	for(int i=1; i<=n; ++i) {
    
		for(int j=1; j<=n; ++j) {
    
			scanf("%d",&x);
			b[i][j]=x;
		}
	}
	ll ans=0;
	for(int i=1; i<=n; ++i) {
    
		for(int j=1; j<=n; ++j) {
    
			for(int k=1; k<=n; ++k) {
    
				if(j==k)
					a[j][k]=(aa[j][k]^b[k][i]);
				else a[j][k]=aa[j][k];
			}
		}
		ans+=Gauss();
	}
	ll sum=qpow(2ll,n*n-ans);
	printf("%lld",sum);
	return 0;
}

C-Stone Game

签到题，不难想到把1和2先合在一起，剩下的再和3合是最优的。

#include <bits/stdc++.h>
using namespace std;
long long x,y,z;
int main()
{
    
    cin>>x>>y>>z;
    if (x==y) 
    {
    
        cout<<x*2;
    }
    else if (x<y)
    {
    
        long long ans=x*2+(y-x)/3*6;
        if ((y-x)%3==2) ans+=4;
        cout<<ans;
    }
    else {
    
        long long ans=y*2+(x-y)/3*3;
        if ((x-y)%3==2) ans++;
        cout<<ans;
    }
    return 0;
}

D-Fight against involution

结构体排序得到每个人在最优情况下拿到的成绩，然后为了减轻内卷，把字数降到最低，此时再统计到对答案的贡献即可。

#include <bits/stdc++.h>
using namespace std;
long long maxi,ans,p,n;
struct dat
{
    
    long long l,r;
}a[200005];
bool cmp(dat a,dat b)
{
    
    return a.r<b.r;
}
int main()
{
    
    cin>>n;
    for (int i=1;i<=n;++i)
    {
    
        scanf("%lld%lld",&a[i].l,&a[i].r);
    }
    sort(a+1,a+1+n,cmp);
    maxi=a[1].l; p=1;
    for (int i=2;i<=n;++i)
        if (a[i].r==a[i-1].r)
            maxi=max(maxi,a[i].l);
        else {
    
            ans+=maxi*(i-p);
            p=i;
            maxi=max(maxi,a[i].l);
        }
    ans+=maxi*(n-p+1);
    cout<<ans;
    return 0;
}

G-Xor Transformation

显然我们可以把X补到二进制全是1的情况，设为$mx=X\oplus a$，同理有$mx=Y\oplus b$ ，a,b即为答案。注意long long边界。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int read(){
    	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';ch=getchar();}return x*f;}
void write(int x){
    if(x>9) write(x/10);putchar(x%10+'0');}

int n,m;
signed main(){
    
	//cin>>n>>m;
	n=read();m=read();
	int mx=1,tmp=0;
	while(mx<n) mx=mx*2ll+1;
	for(int i=0;i<=62;i++){
    
		if((mx&(1ll<<i))&&!(n&(1ll<<i))){
    
			tmp|=(1ll<<i);
		}
	}
	puts("2");
	write(tmp);putchar(' ');
	//cout<<tmp<<" ";
	tmp=0;
	for(int i=0;i<=62;++i){
    
		if((mx&(1ll<<i))&&!(m&(1ll<<i))){
    
			tmp|=(1ll<<i);
		}
	}
	write(tmp);putchar(' ');
	//cout<<tmp<<" \n";
	return 0;
}

/*
1000000000000000000 1

1000000000000000000 1000000000000000000
*/

J-Tree Constructer

不懂为啥大家都想到了二分图，我看到就觉得乱搞。我们从一个点随机赋值然后跑dfs，对于边$(u,v)$，初始化$a[v]=a[u]取补$，然后$a[u]$的所有0位随机变成1，最后$O(n^2) $check一下，就做完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=100;
int n,mp[N][N],a[N],U[N],V[N];
vector<int>G[N]; 

int read(){
    	int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){
    if(ch=='-') f=f*-1;ch=getchar();}while(ch>='0'&&ch<='9'){
    x=x*10+ch-'0';ch=getchar();}return x*f;}
void write(int x){
    if(x>9) write(x/10);putchar(x%10+'0');}

inline bool check(){
      //检查图是否正确 O(n^2) 
	for(int i=0;i<n;++i){
    
		for(int j=i+1;j<n;++j){
    
			if(mp[i][j]^((a[i]|a[j])==(1ll<<60)-1)){
    
				return false;	
			}
		}
	}
	return true;
}

void dfs(int x,int v){
    
	a[x]=v;
	for(auto to:G[x]){
    
		if(a[to]) continue;
		int tmp=((1ll<<60)-1)^a[x];
		for(int j=0;j<60;++j){
    
			if(!(tmp&(1ll<<j))&&(rand()&1))
			tmp|=(1ll<<j);
		}
		dfs(to,tmp);
	}
}

signed main(){
    
	srand(time(0));
	n=read();
	//n=100;
	for(int i=0,u,v;i<n-1;++i){
    
		u=read();v=read();
		u--;v--;
	//	u=0;v=i+1;
		G[u].emplace_back(v);
		G[v].emplace_back(u);
		mp[u][v]=mp[v][u]=1;
	}
	while(1){
    
		memset(a,0,sizeof(a));
		int tmp=0;
		for(int j=0;j<60;++j){
    
			if(rand()&1) tmp|=(1ll<<j);
		}
		dfs(0,tmp);	
		if(check()) break;
	}
	for(int i=0;i<n;++i) write(a[i]),putchar(" \n"[i==n-1]);
	return 0;
} 

L-Bit Sequence

这个范围不难想到数位dp，因为m的范围只有100，所以我们可以暴力计算L后六位所有情况的答案，其余位置对答案的贡献都是固定的。剩下就是数位dp的板子了。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int dp[64][2][2][2];
int bi[64],a[101],m,L;

int calc(int lim,int s,int t){
    
	int res=0,hi=lim?(L%128):127;
	for(int i=0;i<=hi;++i){
     //枚举低6位 
		int f=1;
		for(int j=0;j<m&&f;++j){
    
			if(i+j<128) f&=(__builtin_parity(i+j)^s)==a[j];
			else f&=(__builtin_parity(i+j)^s^t)==a[j];
		}
		res+=f;
	}
	return res;
}

int dfs(int pos,int lim,int s,int t){
     
	if(dp[pos][lim][s][t]!=-1) return dp[pos][lim][s][t];
	if(pos<=6) return dp[pos][lim][s][t]=calc(lim,s,t);
	int res=0;
	int up=lim?bi[pos]:1;
	for(int i=0;i<=up;++i){
    
		res+=dfs(pos-1,lim&&i==up,s^i,i&(!t));
	}
	return dp[pos][lim][s][t]=res;
}

int solve(){
    
	memset(dp,-1,sizeof(dp));
	int len=0,tmp=L;
	while(tmp){
    
		bi[len++]=tmp&1;
		tmp>>=1;
	}
	return dfs(len-1,1,0,0);
}

signed main(){
    
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;
	cin>>T;
	while(T--){
    
		cin>>m>>L;
		for(int i=0;i<m;++i) cin>>a[i];
		cout<<solve()<<"\n";
	}
	return 0;
} 

M-Cook Pancakes!

签到题，贪心地放满锅是最优的，模拟一下这个过程即可。

#include<bits/stdc++.h>
using namespace std;

int n,k;
queue<int>q,p,tmp;

signed main(){
    
	cin>>n>>k;
	int ans=0;
	for(int i=1;i<=n;++i) q.emplace(i);
	while(q.size()||p.size()){
    
		for(int i=1;i<=k;++i){
    
			if(q.size()){
    
				tmp.emplace(q.front());
				q.pop();
			}else if(p.size()){
    
				p.pop();
			}
		}
		while(tmp.size()) p.emplace(tmp.front()),tmp.pop();
		++ans;
	}
	cout<<ans<<"\n";
	return 0;
}