国庆欢乐赛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