温馨提示，先做T4

0225题解

T1

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int dp[1009][1009];
int a[1009];
int main(){
	//freopen("10.in","r",stdin);
	//freopen("10.out","w",stdout);
	int m,s,maxx;cin>>m>>s>>maxx;
	dp[0][s]=1;
	for(int i=1;i<=m;i++)cin>>a[i];
	for(int i=1;i<=m;i++){
		for(int j=0;j<=maxx;j++){
			if(dp[i-1][j]){
				if(j+a[i]<=maxx)dp[i][j+a[i]]=1;
				if(j-a[i]>=0)dp[i][j-a[i]]=1;
			} 
		}
	}
	for(int i=maxx;i>=0;i--){
		if(dp[m][i]){
			cout<<i;
			return 0;
		}
	}
	cout<<-1;
	return 0;
}

T2

#include<bits/stdc++.h>
#define ll long long
#define scnaf scanf
using namespace std;
int dp[1000000],ttime[1000000],tx[1000000],ty[1000000];
int main(){
//	freopen("5.in","r",stdin);
//	freopen("5.out","w",stdout);
	int m,n;scnaf("%d%d",&m,&n);
	for(int i=1;i<=n;i++){
		scnaf("%d%d%d",&ttime[i],&tx[i],&ty[i]);
		dp[i]=1;
	}
	int ans=1;
	for(int i=2;i<=n;i++){
		for(int j=1;j<i;j++){
			if(abs(tx[i]-tx[j])+abs(ty[i]-ty[j])<=ttime[i]-ttime[j]){
				dp[i]=max(dp[i],dp[j]+1);
				ans=max(ans,dp[i]);
			}
		}
	}cout<<ans;
	return 0;
}

T3

#include<bits/stdc++.h>
using namespace std;
#define ll long long
	
	#define int long long

int read(){int d=1,k=0;char c=getchar();
while(!(c>='0' and c<='9' or c=='-'))c=getchar();if(c=='-')d=-1,c=getchar();
while(c>='0' and c<='9')k=(k<<3)+(k<<1)+(c^48),c=getchar();return d*k;}

const int mod=998244353,G=3,g1=332748118;
int a[1000000],jc[1000000],n,k;
int ksm(int x,int k){
	int re=1;while(k){
		if(k&1)re=re*x%mod;
		k>>=1;x=x*x%mod;
	}return re;
} 
int c(int x,int y){return jc[x]*ksm(jc[x-y]*jc[y]%mod,mod-2)%mod;}
int f[1000000],g[1000000],ans[1000000]; 
int r[1000000],l,N=1;
void ntt(int *u,int type){
	for(int i=0;i<=N;i++)if(i<r[i])swap(u[i],u[r[i]]);
	for(int mid=1;mid<N;mid<<=1){
		int w=ksm((type==1?G:g1),(mod-1)/(mid*2));
		for(int i=0;i<N;i+=2*mid){
			int e=1;for(int j=0;j<mid;j++,e=e*w%mod){
				int x=u[i+j],y=u[i+j+mid]*e%mod;
				u[i+j]=x+y;u[i+j]%=mod;
				u[i+j+mid]=x-y+mod;u[i+j+mid]%=mod;
			}
		}
	}
}
int k1[1000000];
signed main(){	
	freopen("10.in","r",stdin);
	freopen("10.out","w",stdout);
	n=read(),k=read();
	jc[0]=1;for(int i=1;i<=min(900000ll,n+k+2);i++)jc[i]=jc[i-1]*i%mod;
	for(int i=1;i<=n;i++)a[i]=read();
	
	k1[0]=k-1;for(int i=1;i<=n;i++)k1[i]=k1[i-1]*((k-1+i)%mod)%mod;
	int tg=ksm(k1[0],mod-2);g[0]=1;
	for(int i=1;i<=n;i++)g[i]=k1[i]*tg%mod*ksm(jc[i],mod-2)%mod;
	for(int i=1;i<=n;i++)f[i]=g[i-1]*a[i]%mod;
	if(k==1){
		for(int i=1;i<=n;i++)f[i]=a[i]*c(i+k-2,k-1);
		for(int i=0;i<=n;i++)g[i]=c(i+k-1,k-1);
	}
	
	while(N<=n*2)N<<=1,l++;
	for(int i=0;i<=N;i++)r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	ntt(f,1),ntt(g,1);for(int i=0;i<=N;i++)ans[i]=f[i]*g[i]%mod;
	ntt(ans,-1);int inv=ksm(N,mod-2);
	for(int i=1;i<=n;i++)printf("%lld ",ans[i]*inv%mod);
	return 0;
}

T4

#include<bits/stdc++.h>
using namespace std;
#define ll long long
	#define int long long
int read(){int d=1,k=0;char c=getchar();
while(!(c>='0' and c<='9' or c=='-'))c=getchar();if(c=='-')d=-1,c=getchar();
while(c>='0' and c<='9')k=(k<<3)+(k<<1)+(c^48),c=getchar();return d*k;}
const int mod=1e9+7;
set<int>L,R;
map<int,int>al,ar;
int ans=1,n;
queue<int>q;
char s[11];
signed main(){
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	L.insert(-1e17),R.insert(1e17);
	n=read();for(int i=1;i<=n;i++){
		scanf("%s",s+1);
		int x=read();
		if(s[2]=='C'){
			if(al[x]){
				al[x]=0;
				if((*L.rbegin())==x){
					L.erase(x);
					while(q.size())R.insert(q.front()),ar[q.front()]=1,q.pop();
				}else{cout<<0;return 0;}
			}else if(ar[x]){
				ar[x]=0;
				if((*R.begin())==x){
					R.erase(x);
					while(q.size())L.insert(q.front()),al[q.front()]=1,q.pop();
				}else{cout<<0;return 0;}
			}else{
				ans=ans*2%mod;
				while(q.size()){
					int u=q.front();q.pop();
					if(u==x)continue;
					if(u<x){
						al[u]=1;
						L.insert(u);
					}else{
						ar[u]=1;
						R.insert(u);
					}
				}
			}
		}else{
			if(x<(*L.rbegin())){
				al[x]=1;
				L.insert(x);
			}else if(x>(*R.begin())){
				ar[x]=1;
				R.insert(x);
			}else q.push(x);
		}
	}
	ans=(ans*(1+q.size()))%mod;
	cout<<ans;
	return 0;
}