code

T1 duel

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e5+10;

ll n,r[maxn];
ll h[maxn],top;
ll c[maxn];
ll ans;

int main(){
	freopen("duel.in","r",stdin);
	freopen("duel.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>r[i];
	sort(r+1,r+n+1);
	for(int i=1;i<=n;i++){
		if(r[i]!=r[i-1])top++;
		h[top]++;
	}
	for(int i=1;i<=top;i++)c[i]=h[i];
	for(int now=1;now<=n;now++){
		for(int i=now+1;i<=n;i++){
			if(c[i]>=h[now]){
				c[i]-=h[now];
				h[now]=0;
				break;
			}
			else {
				h[now]-=c[i];
				c[i]=0;
			}
		}
	}
	for(int i=1;i<=top;i++)ans+=h[i];
	cout<<ans;
} 

T2 detect

#include <bits/stdc++.h>
using namespace std;
#define ll int
const int maxn=1e5+10;

ll t;
ll n,m,l,x;
ll d[maxn],v[maxn],a[maxn],p[maxn];

struct node{
	ll s,f; 
	bool operator < (const node &o){
		if(f!=o.f)return f<o.f;
		return s>o.s;
	}
}c[maxn];
node k[maxn];

bool istoofast(ll v0,ll s0 /*s=p[j]-d[i]*/ ,ll a0){
	if(s0<0)return false;
	if(a0<0&&1ll*2*a0*s0+1ll*v0*v0<0)return false;
	return ((1ll*2*a0*s0)>(1ll*x*x-1ll*v0*v0));
}

void calc(ll i){
	if(a[i]>0){
		ll lft=1,rht=m,ans=m+1;
		while(lft<=rht){
			ll mid=lft+rht>>1;
			if(istoofast(v[i],p[mid]-d[i],a[i]))rht=mid-1,ans=mid;
			else lft=mid+1;
		}
		c[i].s=ans;c[i].f=m;
	}
	if(a[i]<0){
		ll lft=1,rht=m,ans=-1;
//		while(lft<=rht){
//			ll mid=lft+rht>>1;
//			if(istoofast(v[i],p[mid]-d[i],a[i]))lft=mid+1,ans=mid;
//			else rht=mid-1;
//		}
		for(int y=m;y>=1;y--){
			if(istoofast(v[i],p[y]-d[i],a[i])){
				ans=y;
				break;
			}
		}
		c[i].f=ans;
		lft=1,rht=m,ans=1;
		while(lft<=rht){
			ll mid=lft+rht>>1;
			if(p[mid]>=d[i])rht=mid-1,ans=mid;
			else lft=mid+1;
		}
		c[i].s=ans;
	}
	if(a[i]==0){
		if(v[i]<=x)c[i].f=-1;
		else {
			ll lft=1,rht=m,ans=1;
			while(lft<=rht){
				ll mid=lft+rht>>1;
				if(p[mid]>=d[i])rht=mid-1,ans=mid;
				else lft=mid+1;
			}
			c[i].s=ans;
			c[i].f=m;
		}
	}
	return ;
}

void solve(){
//	cout<<v[4]<<' '<<p[3]-d[4]<<' '<<a[4]<<endl;
//	cout<<v[4]<<' '<<p[4]-d[4]<<' '<<a[4]<<endl;
//	cout<<v[4]<<' '<<p[5]-d[4]<<' '<<a[4]<<endl;
//	for(int i=1;i<=n;i++)cout<<c[i].s<<' '<<c[i].f<<endl;
	ll ans=0,sum=1;
	for(int i=1;i<=n;i++){
		if(c[i].s<=c[i].f)k[++ans].s=c[i].s,k[ans].f=c[i].f;
	}
	printf("%d ",ans);
	if(ans==0){
		printf("0");
		cout<<endl;
		return ;
	}
	sort(k+1,k+ans+1);
//	for(int i=1;i<=ans;i++)cout<<k[i].s<<' '<<k[i].f<<endl;
	int rpt;
	rpt=k[1].f;
	for(int i=2;i<=ans;i++){
		if(rpt<k[i].s)sum++,rpt=k[i].f;
	}
	printf("%d",m-sum);
	cout<<endl;
	return ;
}

int main(){
	freopen("detect.in","r",stdin);
	freopen("detect.out","w",stdout);
	cin>>t;
	while(t--){
		scanf("%d%d%d%d",&n,&m,&l,&x);
		for(int i=1;i<=n;i++)scanf("%d%d%d",&d[i],&v[i],&a[i]);
		for(int i=1;i<=m;i++)scanf("%d",&p[i]);
		
		bool isA=1;
		for(int i=1;i<=n;i++){
			if(a[i]!=0){
				isA=0;break;
			}
		}
		if(isA){
			//3~4 20pts
			ll pm=p[m],ans=0;
			for(int i=1;i<=n;i++){
				if(v[i]>x&&d[i]<=pm)ans++;
			}
			printf("%d ",ans);
			if(ans==0)printf("%d",m);
			else printf("%d",m-1);
			cout<<endl;
			continue; 
		}
		//(maybe) O(nlogn)
		for(int i=1;i<=n;i++){
			calc(i);
		}
		solve();
	}
} 

T3 color

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+10;
const int maxn1=2e3+10;

ll t;
ll ans,a[maxn],n;
int p[maxn];//0=red 1=blue
ll dp[maxn1][maxn1][2];

void dfs(int pos){
	if(pos>n){
		ll sum=0;
		for(int i=1;i<=n;i++){
			for(int j=i-1;j>=1;j--){
				if(p[j]==p[i]){
					if(a[j]==a[i])sum+=a[i];
					break;
				}
			}
		}
		ans=max(sum,ans);
		return ;
	}
	p[pos]=0;
	dfs(pos+1);
	p[pos]=1;
	dfs(pos+1);
	p[pos]=0;
	return ;
}

int main(){
	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout);
	cin>>t;
	while(t--){
		cin>>n;
		for(int i=1;i<=n;i++)cin>>a[i];
		ans=0;
		if(n<=15){
			//subtask1 1~4,worth 20 pts.
			dfs(1);
			cout<<ans<<endl;
			continue; 
		}
		if(n<=2000){
			for(int i=1;i<=n;i++) for(int j=1;j<=n;j++)dp[i][j][0]=dp[i][j][1]=0;
			for(int s=1;s<n;s++){
				for(int j=1;j<=s-1;j++){
					dp[s+1][j][1]=dp[s][j][1]+a[s+1]*(a[s]==a[s+1]?1:0);
					dp[s+1][j][0]=dp[s][j][0]+a[s+1]*(a[s]==a[s+1]?1:0);
				}
				int j=s;
				for(int k=0;k<=1;k++){
					dp[s+1][j][k]=dp[s][j][k]+a[s+1]*(a[s]==a[s+1]?1:0);
					for(int t=1;t<j;t++){
						dp[s+1][j][k]=max(dp[s+1][j][k],dp[s][t][1-k]+a[s+1]*(a[t]==a[s+1]?1:0));
					}
				}
			}
			for(int i=1;i<n;i++)ans=max(ans,max(dp[n][i][0],dp[n][i][1]));
			cout<<ans<<endl;
			continue;
		}
	}
} 

T4 arena

(没写)