国庆欢乐赛1

Done OI Start at: 2024-10-3 14:00 3.5 hour(s) Host: 33

OI赛制,注意freopen

//如果一个图联通,那么一定能从起点出发,所有边走两遍回到起点 
// 
#include <bits/stdc++.h> 
using namespace std;
#define int long long
const int N = 1e5+5;
vector<int>e[N];
int book[N],n,m,T;
void dfs(int x)
{
	book[x] = 1;
	for(int i=0;i<e[x].size();i++){
		int v = e[x][i];
		if(!book[v]){
			book[v] = 1;
			dfs(v);
		}
	}
}
signed main()
{
	freopen("journey.in","r",stdin);
	freopen("journey.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		for(int i=1;i<=n;i++){
			e[i].clear();
			book[i] = 0;
		}
		for(int i=1;i<=m;i++){
			int x,y;
			cin>>x>>y;
			e[x].push_back(y);
			e[y].push_back(x);
		}
		dfs(1);
		int res = 0,flag=0;
		for(int i=1;i<=n;i++){
			if(book[i]==0 && e[i].size()>0){
				flag = 1;
				break;
			}
			res+=(e[i].size()*(e[i].size()-1)/2);
		}
		if(flag==1){
			cout<<0<<endl;
		}
		else{
			cout<<res<<endl;
		}
	}

	return 0;
}
/*
从起点走n-1步得到的所有和mp[w] = 
从终点走n-1步得到的所有和 
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 25;
int h[N][N],s[N][N];
int T,n,m,res;
map<int,int>mp[N];
void dfs1(int x,int y,int val)
{
	//1,1   (x+y)==n-1
	if(x+y==n+1){
		if(mp[x].count(val)==0){
			mp[x][val] = 1;
		}
		else mp[x][val]++;
		return;
	}
	dfs1(x,y+1,val^h[x][y]);
	dfs1(x+1,y,val^s[x][y]);
}
void dfs2(int x,int y,int val)
{
	//n,n   
	if(x+y==n+1){
		res+=mp[x][m^val];
		return;
	}
	dfs2(x,y-1,val^h[x][y-1]);
	dfs2(x-1,y,val^s[x-1][y]);
}
signed main()
{
	freopen("explore.in","r",stdin);
	freopen("explore.out","w",stdout);
	cin>>T;
	while(T--){
		cin>>n>>m;
		res = 0;
		for(int i=1;i<=n;i++)mp[i].clear();
		for(int i=1;i<=n;i++){
			for(int j=1;j<n;j++){
				cin>>h[i][j];
			}
		}
		for(int i=1;i<n;i++){
			for(int j=1;j<=n;j++){
				cin>>s[i][j];
			}
		}
		dfs1(1,1,0);
		dfs2(n,n,0);
		cout<<res<<endl;
	}
	return 0;
}

Files

Filename Size
ex_explore1.in 19 Bytes
ex_explore1.out 3 Bytes
ex_explore2.in 747 Bytes
ex_explore2.out 4 Bytes
ex_journey1.in 23 Bytes
ex_journey1.out 3 Bytes
ex_journey2.in 2 KiB
ex_journey2.out 6 Bytes
ex_partition1.in 20 Bytes
ex_partition1.out 15 Bytes
ex_partition2.in 103 Bytes
ex_partition2.out 60 Bytes
ex_perm1.in 13 Bytes
ex_perm1.out 7 Bytes
ex_perm2.in 23 Bytes
ex_perm2.out 21 Bytes
Status
Done
Rule
OI
Problem
4
Start at
2024-10-3 14:00
End at
2024-10-3 17:30
Duration
3.5 hour(s)
Host
Partic.
33