I
转化为图论模型来解决问题。把给定二元组当作一条边，那么显然，如果对于一个连通块如果其是一棵树，那么就会给答案增加这个连通块大小-1的贡献、如果是一个仙人掌，那么就会给答案增加连通块大小的贡献。拿并查集即可维护我们所需的信息。由于给定二元组的值域比较大，所以需要离散化处理。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
#define PII pair <int,int>
#define fr first
#define sc second
#define mp make_pair
const int N=4e5+7;
vector<ll> v;
int getid(ll x) {return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
PII a[N];
int fa[N],rk[N];
int vis[N],loop[N];
int find(int x){ return fa[x]==x? x:(fa[x]=find(fa[x]));}
void merge(int x,int y){
x=find(x);y=find(y);
if(x!=y){
if(rk[x]>=rk[y]){
loop[x]=max(loop[y],loop[x]);
fa[y]=x;
rk[x]+=rk[y];
}else{
loop[y]=max(loop[y],loop[x]);
fa[x]=y;
rk[y]+=rk[x];
}
}
}
int main(){
int T=input(),cas=0;
while(T--){
int n=input();
for(int i=1;i<=4*n;i++){
fa[i]=i,rk[i]=1;vis[i]=0,loop[i]=0;
}
v.clear();
for(int i=1;i<=n;i++){
a[i].fr=input(),a[i].sc=input();
v.push_back(a[i].fr),v.push_back(a[i].sc);
}
sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end());
for(int i=1;i<=n;i++){
int u=getid(a[i].fr),v=getid(a[i].sc);
if(find(u)==find(v)) loop[find(u)]=1;
merge(u,v);
}
int Ans=0;
for(int i=1;i<=v.size();i++){
if(!vis[find(i)]){
Ans+=rk[find(i)]-(loop[find(i)]==0);
vis[find(i)]=1;
}
}
printf("Case #%d: %d
",++cas,Ans);
}
}
K
求最多人数下的最大盈利。那么显然(b[1])就是最大人数。要求最大收益，我们只需要计算(a[i])的前缀和，从最大的前缀和往前从大到小取就是答案。显然我们可以用前缀的相关科技维护前缀最值和索引。本题数据范围超过了ll，需要使用__int128或者其它语言解决。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
#define LL __int128
const int N=1e5+7;
int t[N<<4];
int n;
LL a[N],b[N],sum[N];
LL amx[N],bmi[N];
inline void write(__int128 x){
if(x<0){
putchar('-');
x=-x;
}
if(x>9)
write(x/10);
putchar(x%10+'0');
}
int main(){
int T=input(),cas=0;
while(T--){
n=input();
for(int i=1;i<=n;i++) a[i]=input();
for(int i=1;i<=n;i++) b[i]=input();
sum[1]=a[1];
for(int i=2;i<=n;i++) sum[i]=sum[i-1]+a[i];
amx[1]=1,bmi[1]=b[1];
for(int i=2;i<=n;i++){
amx[i]=amx[i-1];
if(sum[i]>sum[amx[i]]) amx[i]=i;
bmi[i]=bmi[i-1];
if(b[i]<bmi[i]) bmi[i]=b[i];
}
int now=amx[n];
LL Ans=0,cnt=0;
while(now!=1){
Ans=Ans+sum[now]*(bmi[now]-cnt);
cnt+=(bmi[now]-cnt);
now=amx[now-1];
}
Ans=Ans+sum[1]*(bmi[1]-cnt);
cnt+=(bmi[1]-cnt);
printf("Case #%d: ",++cas);
write(cnt);printf(" ");
write(Ans),printf("
");
}
}
G
大模拟题。本题可以根据性质有更好的做法。这里讲一下我比赛的时候的做法。首先我们发现一共有4种状态，每个状态只有3种类别，我们很容易的想到hash。由于数据范围很小，我们这里可以直接hash。另外我们发现，当我们知道两个状态时，第三状态我们可以直接计算出来，所以我们可以(n^2)的枚举卡片，用hash找第三张卡片。但是这里有个问题，当我们枚举某一张卡片有通配符时，我们还需要额外枚举通配符是什么，这里我们不妨猜测这些状态很小，那么我们只需要随机通配符是什么就行了，我大概随机50次就过了。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll input(){
ll x=0,f=0;char ch=getchar();
while(ch<'0'||ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return f? -x:x;
}
string s1[4]={"[*]","[one]","[two]","[three]"};
string s2[4]={"[*]","[diamond]","[squiggle]","[oval]"};
string s3[4]={"[*]","[solid]","[striped]","[open]"};
string s4[4]={"[*]","[red]","[green]","[purple]"};
string s="";
const int N=300;
struct card{
int a,b,c,d;
}a[N];
int mp[10007];
void dfs(int dep,int x,int pos){
if(dep==5){mp[x]=pos;return;}
if(dep==1){
if(a[pos].a==0){
for(int i=1;i<=3;i++) dfs(dep+1,x*10+i,pos);
}else dfs(dep+1,x*10+a[pos].a,pos);
}
if(dep==2){
if(a[pos].b==0){
for(int i=1;i<=3;i++) dfs(dep+1,x*10+i,pos);
}else dfs(dep+1,x*10+a[pos].b,pos);
}
if(dep==3){
if(a[pos].c==0){
for(int i=1;i<=3;i++) dfs(dep+1,x*10+i,pos);
}else dfs(dep+1,x*10+a[pos].c,pos);
}
if(dep==4){
if(a[pos].d==0){
for(int i=1;i<=3;i++) dfs(dep+1,x*10+i,pos);
}else dfs(dep+1,x*10+a[pos].d,pos);
}
}
void init(int n){
for(int i=1;i<=n;i++){
cin>>s;
string res="";
int dep=1;
for(int j=0;j<s.length();j++){
res+=s[j];
if(res[0]=='['&&res[res.length()-1]==']'){
if(dep==1){
for(int k=0;k<=3;k++)
if(res==s1[k]) a[i].a=k;
dep=2;res="";
continue;
}
if(dep==2){
for(int k=0;k<=3;k++)
if(res==s2[k]) a[i].b=k;
dep=3;res="";
continue;
}
if(dep==3){
for(int k=0;k<=3;k++)
if(res==s3[k]) a[i].c=k;
dep=4;res="";
continue;
}
if(dep==4){
for(int k=0;k<=3;k++)
if(res==s4[k]) a[i].d=k;
dep=1;res="";
continue;
}
}
}
dfs(1,0,i);
}
}
int main(){
int T=input(),cas=0;
while(T--){
int n=input();
memset(mp,0,sizeof(mp));
init(n);
int flag=0;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
for(int x=0;x<=50;x++){
int a0=a[i].a,a1=a[j].a,a2;
if(a0==0) a0=rand()%3+1;
if(a1==0) a1=rand()%3+1;
if(a0==a1) a2=a0;
else{
for(int i=1;i<=3;i++){
if(i!=a0&&i!=a1){
a2=i;break;
}
}
}
int b0=a[i].b,b1=a[j].b,b2;
if(b0==0) b0=rand()%3+1;
if(b1==0) b1=rand()%3+1;
if(b0==b1) b2=b0;
else{
for(int i=1;i<=3;i++){
if(i!=b0&&i!=b1){
b2=i;break;
}
}
}
int c0=a[i].c,c1=a[j].c,c2;
if(c0==0) c0=rand()%3+1;
if(c1==0) c1=rand()%3+1;
if(c0==c1) c2=c0;
else{
for(int i=1;i<=3;i++){
if(i!=c0&&i!=c1){
c2=i;break;
}
}
}
int d0=a[i].d,d1=a[j].d,d2;
if(d0==0) d0=rand()%3+1;
if(d1==0) d1=rand()%3+1;
if(d0==d1) d2=d0;
else{
for(int i=1;i<=3;i++){
if(i!=d0&&i!=d1){
d2=i;break;
}
}
}
if(mp[a2*1000+b2*100+c2*10+d2]!=0){
if(i==j||mp[a2*1000+b2*100+c2*10+d2]==i||mp[a2*1000+b2*100+c2*10+d2]==j) continue;
printf("Case #%d: %d %d %d
",++cas,i,j,mp[a2*1000+b2*100+c2*10+d2]);
flag=1;
break;
}
if(flag==1) break;
}
if(flag==1) break;
}
if(flag==1) break;
}
if(!flag) printf("Case #%d: -1
",++cas);
}
}