• 【超好懂的比赛题解】第 45 届国际大学生程序设计竞赛（ICPC）亚洲区域赛（济南）

    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
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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73

    C-Stone Game

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

    #include 
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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    D-Fight against involution

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

    #include 
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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    G-Xor Transformation

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

    #include
#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=0;
	for(int i=0;i<=62;++i){
		if((mx&(1ll<<i))&&!(m&(1ll<<i))){
			tmp|=(1ll<<i);
		}
	}
	write(tmp);putchar(' ');
	//cout<
	return 0;
}

/*
1000000000000000000 1

1000000000000000000 1000000000000000000
*/

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    J-Tree Constructer

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

    #include
#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;
} 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    L-Bit Sequence

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

    #include
#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;
} 

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53

    M-Cook Pancakes!

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

    #include
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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
  • 相关阅读:
    MySQL自增主键和手动生成主键区别
    SpringCloud01：Eureka的使用
    【MySQL】MySQL 发展历程和主流分支
    Python之socket简玩
    解析ERP管理系统的实施难题及解决方案
    怎样生成分布式的流水ID
    PMP工具与技术总结
    go 反射 reflect 包
    第二章操作系统测试
    Windows安装C语言环境
  • 原文地址：https://blog.csdn.net/SC_Linno/article/details/126893412