rt,此代码:
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
int n,m;
char dan[100007],dan1[100007];
char qnot(char l)
{
if(l=='T') return 'F';
if(l=='F') return 'T';
return 'U';
}
pair<char,pair<int,int> > table[100007];
int main()
{
int c,t;
cin>>c>>t;
while(t--)
{
int ans=0;
cin>>n>>m;
memset(dan,'T',sizeof(dan));
if(c==3||c==4)
{
for(int i=0;i<m;i++)
{
char ch;
int ind;
cin>>ch>>ind;
dan[ind-1]=ch;
}
for(int i=0;i<n;i++)
{
if(dan[i]=='U') ans++;
}
}else if(c==5||c==6){
// for(int i=0;i<m;i++)
// {
// char ch;
// int ind;
// cin>>ch>>ind;
// if(ch=='U') dan[ind]=ch;
// else
// {
// int y;
// cin>>y;
// dan[ind]=dan[y];
// }
// }
// for(int i=1;i<=n;i++)
// {
//// cout<<dan[i]<<endl;
// if(dan[i]=='U') ans++;
// }
//// cout<<endl;
for(int i=0;i<m;i++)
{
char op;
int x;
cin>>op>>x;
if(op=='U') dan[x-1]=op,table[i]=mp(op,mp(x,0));
else
{
int y;
cin>>y;
dan[x-1]=dan[y-1];
table[i]=mp(op,mp(x,y));
}
}
for(int i=0;i<n;i++) dan1[i]=dan[i];
for(int i=0;i<m;i++)
{
char op;
int x;
op=table[i].first;
x=table[i].second.first;
if(op=='U') dan1[x-1]=op;
else
{
int y;
y=table[i].second.second;
dan1[x-1]=dan1[y-1];
}
}
int eps=100;
if(n>9000) eps=89;
if(n>50000) eps=80;
if(n>70000) eps=73;
while(eps--)
{
swap(dan1,dan);
for(int i=0;i<n;i++) dan1[i]=dan[i];
for(int i=0;i<m;i++)
{
char op;
int x;
op=table[i].first;
x=table[i].second.first;
if(op=='U') dan1[x-1]=op;
else
{
int y;
y=table[i].second.second;
dan1[x-1]=dan1[y-1];
}
}
}
for(int i=0;i<n;i++) if(dan[i]!=dan1[i]||dan1[i]=='U') ans++;
}else{
for(int i=0;i<m;i++)
{
char op;
int x;
cin>>op>>x;
if(op=='T'||op=='F'||op=='U') dan[x-1]=op,table[i]=mp(op,mp(x,0));
else
{
int y;
cin>>y;
dan[x-1]=(op=='-'?qnot(dan[y-1]):dan[y-1]);
table[i]=mp(op,mp(x,y));
}
}
for(int i=0;i<n;i++) dan1[i]=dan[i];
for(int i=0;i<m;i++)
{
char op;
int x;
op=table[i].first;
x=table[i].second.first;
if(op=='T'||op=='F'||op=='U') dan1[x-1]=op;
else
{
int y;
y=table[i].second.second;
dan1[x-1]=(op=='-'?qnot(dan1[y-1]):dan1[y-1]);
}
}
int eps=100;
if(n>10000) eps=80;
while(eps--)
{
swap(dan1,dan);
for(int i=0;i<n;i++) dan1[i]=dan[i];
for(int i=0;i<m;i++)
{
char op;
int x;
op=table[i].first;
x=table[i].second.first;
if(op=='T'||op=='F'||op=='U') dan1[x-1]=op;
else
{
int y;
y=table[i].second.second;
dan1[x-1]=(op=='-'?qnot(dan1[y-1]):dan1[y-1]);
}
}
}
for(int i=0;i<n;i++) if(dan[i]!=dan1[i]||dan1[i]=='U') ans++;
}
cout<<ans<<endl;
}
return 0;
}
获得了90pts的成绩?