2020牛客多校第九场

构造

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int mod=998244353;
const int maxn=2e4+10;
char a[maxn]; 
int b[maxn],n,mmax;
int f(int l,int r)
{
	int s=0,m,sum=0;
	for(int i=l+1;i<=r-1;i++)
	{
		if(a[i]=='(')
		{
			if(s==0)
				m=i;
			s++;
		}
		else if(a[i]==')')
		{
			s--;
			if(s==0)
				sum+=1<<f(m,i);
		}
		else if(a[i]=='2')
		{
			if(a[i+1]!='('&&s==0)
				sum+=2;
		}
	}
	//cout<<sum<<endl;
	return sum;
}
void jf(int x)
{
	int c[200]={},cnt=1;
	c[0]=1;
	for(int i=1;i<=x;i++)
	{
		for(int j=0;j<cnt;j++)
			c[j]*=2;
		for(int j=0;j<cnt;j++)
			c[j+1]+=c[j]/10,c[j]%=10;
		while(c[cnt]>0)
		{
			c[cnt+1]+=c[cnt]/10,c[cnt]%=10;
			cnt++;
		}
	}
	for(int i=0;i<cnt;i++)
		b[i]+=c[i];
	mmax=max(mmax,cnt);
	//cout<<cnt<<endl;
	return ;
}
void solve()
{
	int s=0,l=1,r;
	for(int i=1;i<=n;i++)
	{
		if(a[i]=='(')
		{
			if(s==0)
				l=i;
			s++;
		}
		else if(a[i]==')')
		{
			s--;
			if(s==0)
				jf(f(l,i));
		}
		else if(a[i]=='2')
		{
			if(a[i+1]!='('&&s==0)
				jf(1);
		}
	}
}
int main()
{
    scanf("%s",a+1);
    n=strlen(a+1);
    solve();
    for(int i=0;i<mmax;i++)
    {
    	b[i+1]+=b[i]/10;
    	b[i]%=10;
	}
	while(b[mmax]>0)
	{
		b[mmax+1]+=b[mmax]/10,b[mmax]%=10;
		mmax++;
	}
	for(int i=mmax-1;i>=0;i--)
		printf("%d",b[i]);
    return 0;
}

F.Groundhog Looking Dowdy

尺取

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int mod=1e9+7;
const int maxn=1e6+10;
struct cc{
	int x,id;
}a[2*maxn];
int f[maxn];
bool cmp(cc x,cc y)
{
	return x.x<y.x;
}
int main()
{
    int n,m,cnt=1,x,s=0;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
    	scanf("%d",&x);
    	for(int j=1;j<=x;j++)
    	{
    		scanf("%d",&a[cnt].x);
    		a[cnt++].id=i;
		}
	}
	sort(a+1,a+cnt,cmp);
	int l=1,r=1,mmin=mod;
	s=1;
	f[a[1].id]++;
	while(l<cnt&&r<cnt)
	{
		while(s<m&&r<cnt)
		{
			r++;
			if(f[a[r].id]==0)
				s++;
			f[a[r].id]++;
		}
		if(r<cnt)
			mmin=min(mmin,a[r].x-a[l].x);
		//cout<<mmin<<endl;
		l++;
		if(f[a[l].id]==1)
			s--;
		f[a[l].id]--;
	}
	printf("%d",mmin);
    return 0;
}

I.The Crime-solving Plan of Groundhog

大数

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define sc(a) scanf("%d",&a)
#define pf printf
#define pb push_back
const int N=1e6+10;
const int mod=1e9+7; 
int n;
int a[N];
int b[N];
int ans[N];
int main()
{
	int t;sc(t);
	while(t--)
	{
		sc(n);
		for(int i=1;i<=n;i++)sc(a[i]);
		sort(a+1,a+1+n);
		int x,k;
		for(int i=1;i<=n;i++)
			if(a[i]){
				x=a[i];
				k=i;
				break;
			}
		int cnt=0;
		for(int i=n;i>=k+2;i--)
			b[++cnt]=a[i];
		
		for(int i=k-1;i;i--)
			b[++cnt]=a[i];
		b[++cnt]=a[k+1];
		//cout<<k<<endl;
		//for(int i=1;i<=cnt;i++)cout<<b[i];cout<<endl;
		for(int i=1;i<=cnt;i++)
			ans[i]=b[i]*x;
		for(int i=1;i<cnt;i++)
		{
			ans[i+1]+=ans[i]/10;
			ans[i]%=10;
		}
		while(ans[cnt]>9){
			ans[cnt+1]=ans[cnt]/10;
			ans[cnt]%=10;
			cnt++;
		}
		for(int i=cnt;i;i--)pf("%d",ans[i]);puts("");
		for(int i=1;i<=cnt;i++)
		{
			b[i]=ans[i]=0;
		}
	}
	return 0;
}