I.Interesting Computer Game

并查集

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int mod=1e9+7;
const int maxn=1e5+10;
int a[2*maxn],f[2*maxn],s[2*maxn],m[2*maxn];
struct cc{
	int x,id;
}p[2*maxn];
bool cmp(cc x,cc y)
{
	return x.x<y.x;
}
int find(int x)
{
	while(x!=f[x])
		x=f[x];
	return x;
}
int main()
{
	int t,n,sum,x,y;
	cin>>t;
	for(int ii=1;ii<=t;ii++)
	{
		scanf("%d",&n);
		sum=0;
		for(int i=1;i<=n;i++)
		{
			f[2*i-1]=2*i-1,f[2*i]=2*i;
			s[2*i-1]=0,s[2*i]=0;
			m[2*i-1]=1,m[2*i]=1;
			scanf("%d %d",&a[2*i-1],&a[2*i]);
			p[2*i-1].x=a[2*i-1];
			p[2*i-1].id=2*i-1;
			p[2*i].x=a[2*i];
			p[2*i].id=2*i;
		}
		sort(p+1,p+2*n+1,cmp);
		int cnt=1;
		a[p[1].id]=cnt;
		for(int i=2;i<=2*n;i++)
		{
			if(p[i].x!=p[i-1].x)
				cnt++;
			a[p[i].id]=cnt;
		}
		for(int i=1;i<=n;i++)
		{
			x=find(a[2*i-1]),y=find(a[2*i]);
			f[a[2*i-1]]=x,f[a[2*i]]=y;
			if(x!=y)
				f[x]=y,s[y]+=s[x]+1,m[y]+=m[x];
			else if(x==y)
				s[x]++;
		}
		for(int i=1;i<=2*n;i++)
		{
			if(f[i]==i)
			{
				//cout<<i<<' '<<sum<<' '<<m[i]<<' '<<s[i]<<endl;
				sum+=m[i]-1;
				if(s[i]>=m[i])
					sum++;
			}
		}
		printf("Case #%d: %d\n",ii,sum);
	}
    return 0;
}

K.Kabaleo Lite

ull瞎搞

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
const int mod=1e9+7;
const int maxn=1e5+10;
ll a[maxn],f[maxn],m[maxn];
int b[maxn],mmin[maxn];
int main()
{
	int t,n,cnt;
	ull s;
	scanf("%d",&t);
	for(int ii=1;ii<=t;ii++)
	{
		scanf("%d",&n);
		s=0,cnt=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);
			f[i]=f[i-1]+a[i];
			if(i==1)
				m[i]=f[i];
			else
				m[i]=max(m[i-1],f[i]);
		}
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&b[i]);
			if(i==1)
				mmin[i]=b[i];
			else
				mmin[i]=min(mmin[i-1],b[i]);
		}
		ll mmax=0;
		ll s1=0;
		for(int i=n;i>=1;i--)
		{
			s+=(ull)(m[i]+1e9)*(mmin[i]-cnt);
			s1+=1e9*(mmin[i]-cnt);
			cnt=mmin[i];
		}
		printf("Case #%d: %d ",ii,b[1]);
		if(s1>=s)
			printf("%lld\n",(ll)s-s1);
		else
			cout<<s-s1<<endl; 
	}
    return 0;
}