set做法居然能草过100分？
查看原帖
set做法居然能草过100分？
1123558
grard4楼主2025/4/29 19:38

卡常出奇迹！！！

使用 cin 和 cout 读写（70pts）

#include<bits/stdc++.h>
#define MAXN 1000005
#define MAXM 100005
#define ll long long
#define ull unsigned long long
#define lll __int128
#define ls u<<1
#define rs u<<1|1
#define M (L+R>>1)
#define mk make_pair
#define fir first
#define sec second
#define low(x) (x&(-x))
#define pb push_back
using namespace std;
const int mod=1e9+7,inf=2e9;
const double pi=acos(-1);
int read()
{
	int ret=0,sgn=0,ch=getchar();
	while (!isdigit(ch)) sgn|=ch=='-',ch=getchar();
	while (isdigit(ch)) ret=ret*10+ch-'0',ch=getchar();
	return sgn ? -ret:ret;
}
void write(int x)
{
	static int sta[70];
	if (x<0) {x=-x;putchar('-');}
	int top=0;
	do{sta[top++]=x%10,x/=10;}while(x);
	while (top) putchar(sta[--top]+'0');
}

struct sn
{
	int id,x;
	friend bool operator<(const sn &x,const sn &y)
	{
		if (x.x==y.x) return x.id<y.id;
		else return x.x<y.x;
	}
	friend bool operator>(const sn &x,const sn &y)
	{
		if (x.x==y.x) return x.id>y.id;
		else return x.x>y.x;
	}
}a[MAXN];
int T,n;bool op;
void solve()
{
    if (!op) {op=true,cin>>n;for (int i=1;i<=n;i++) cin>>a[i].x,a[i].id=i;}
    else
    {
		int k;cin>>k;
		for (int i=1;i<=k;i++)
		{
			int x,y;cin>>x>>y;
			a[x].x=y;
		}	
	}
	multiset<sn> s;
	for (int i=1;i<=n;i++) s.insert(a[i]);
	while(s.size()>2)
	{
		sn p=*--s.end(),q=*s.begin();p.x-=q.x;
		if (p>*++s.begin()) s.erase(--s.end()),s.erase(s.begin()),s.insert(p);
		else break;
	} 
	if (s.size()==2) {cout<<1<<endl;return;}
	int ans=s.size(),cnt=0;
	while(s.size()>2)
	{
		cnt++;sn p=*--s.end(),q=*s.begin();p.x-=q.x;
		s.erase(--s.end()),s.erase(s.begin()),s.insert(p);
		if (s.size()==2) break;
		p=*--s.end(),q=*s.begin(),p.x-=q.x;
		if (p>*++s.begin()) break;
	}
	ans-=(cnt&1)^1;
	cout<<ans<<endl;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("0.in","r",stdin);
	freopen("0.out","w",stdout);
	time_t bg=clock();
#endif
	T=read();
	while(T--) solve();
#ifndef ONLINE_JUDGE
	time_t ed=clock()-bg;
	cout<<endl<<"time = "<<ed<<" ms"<<endl;
	fclose(stdin);fclose(stdout);
#endif
	return 0;
}

使用 scanf 和 printf 读写（100pts）

#include<bits/stdc++.h>
#define MAXN 1000005
#define MAXM 100005
#define ll long long
#define ull unsigned long long
#define lll __int128
#define ls u<<1
#define rs u<<1|1
#define M (L+R>>1)
#define mk make_pair
#define fir first
#define sec second
#define low(x) (x&(-x))
#define pb push_back
using namespace std;
const int mod=1e9+7,inf=2e9;
const double pi=acos(-1);
int read()
{
	int ret=0,sgn=0,ch=getchar();
	while (!isdigit(ch)) sgn|=ch=='-',ch=getchar();
	while (isdigit(ch)) ret=ret*10+ch-'0',ch=getchar();
	return sgn ? -ret:ret;
}
void write(int x)
{
	static int sta[70];
	if (x<0) {x=-x;putchar('-');}
	int top=0;
	do{sta[top++]=x%10,x/=10;}while(x);
	while (top) putchar(sta[--top]+'0');
}

struct sn
{
	int id,x;
	friend bool operator<(const sn &x,const sn &y)
	{
		if (x.x==y.x) return x.id<y.id;
		else return x.x<y.x;
	}
	friend bool operator>(const sn &x,const sn &y)
	{
		if (x.x==y.x) return x.id>y.id;
		else return x.x>y.x;
	}
}a[MAXN];
int T,n;bool op;
void solve()
{
    if (!op) {op=true,scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i].x),a[i].id=i;}
    else
    {
		int k;scanf("%d",&k);
		for (int i=1;i<=k;i++)
		{
			int x,y;scanf("%d%d",&x,&y);
			a[x].x=y;
		}	
	}
	multiset<sn> s;
	for (int i=1;i<=n;i++) s.insert(a[i]);
	while(s.size()>2)
	{
		sn p=*--s.end(),q=*s.begin();p.x-=q.x;
		if (p>*++s.begin()) s.erase(--s.end()),s.erase(s.begin()),s.insert(p);
		else break;
	} 
	if (s.size()==2) {puts("1");return;}
	int ans=s.size(),cnt=0;
	while(s.size()>2)
	{
		cnt++;sn p=*--s.end(),q=*s.begin();p.x-=q.x;
		s.erase(--s.end()),s.erase(s.begin()),s.insert(p);
		if (s.size()==2) break;
		p=*--s.end(),q=*s.begin(),p.x-=q.x;
		if (p>*++s.begin()) break;
	}
	ans-=(cnt&1)^1;
	printf("%d",ans),putchar('\n');
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("0.in","r",stdin);
	freopen("0.out","w",stdout);
	time_t bg=clock();
#endif
	T=read();
	while(T--) solve();
#ifndef ONLINE_JUDGE
	time_t ed=clock()-bg;
	cout<<endl<<"time = "<<ed<<" ms"<<endl;
	fclose(stdin);fclose(stdout);
#endif
	return 0;
}

使用快读快写（100pts）

#include<bits/stdc++.h>
#define MAXN 1000005
#define MAXM 100005
#define ll long long
#define ull unsigned long long
#define lll __int128
#define ls u<<1
#define rs u<<1|1
#define M (L+R>>1)
#define mk make_pair
#define fir first
#define sec second
#define low(x) (x&(-x))
#define pb push_back
using namespace std;
const int mod=1e9+7,inf=2e9;
const double pi=acos(-1);
int read()
{
	int ret=0,sgn=0,ch=getchar();
	while (!isdigit(ch)) sgn|=ch=='-',ch=getchar();
	while (isdigit(ch)) ret=ret*10+ch-'0',ch=getchar();
	return sgn ? -ret:ret;
}
void write(int x)
{
	static int sta[70];
	if (x<0) {x=-x;putchar('-');}
	int top=0;
	do{sta[top++]=x%10,x/=10;}while(x);
	while (top) putchar(sta[--top]+'0');
}

struct sn
{
	int id,x;
	friend bool operator<(const sn &x,const sn &y)
	{
		if (x.x==y.x) return x.id<y.id;
		else return x.x<y.x;
	}
	friend bool operator>(const sn &x,const sn &y)
	{
		if (x.x==y.x) return x.id>y.id;
		else return x.x>y.x;
	}
}a[MAXN];
int T,n;bool op;
void solve()
{
    if (!op) {op=true,n=read();for (int i=1;i<=n;i++) a[i].x=read(),a[i].id=i;}
    else
    {
		int k=read();
		for (int i=1;i<=k;i++)
		{
			int x=read(),y=read();
			a[x].x=y;
		}	
	}
	multiset<sn> s;
	for (int i=1;i<=n;i++) s.insert(a[i]);
	while(s.size()>2)
	{
		sn p=*--s.end(),q=*s.begin();p.x-=q.x;
		if (p>*++s.begin()) s.erase(--s.end()),s.erase(s.begin()),s.insert(p);
		else break;
	} 
	if (s.size()==2) {puts("1");return;}
	int ans=s.size(),cnt=0;
	while(s.size()>2)
	{
		cnt++;sn p=*--s.end(),q=*s.begin();p.x-=q.x;
		s.erase(--s.end()),s.erase(s.begin()),s.insert(p);
		if (s.size()==2) break;
		p=*--s.end(),q=*s.begin(),p.x-=q.x;
		if (p>*++s.begin()) break;
	}
	ans-=(cnt&1)^1;
	write(ans),putchar('\n');
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("0.in","r",stdin);
	freopen("0.out","w",stdout);
	time_t bg=clock();
#endif
	T=read();
	while(T--) solve();
#ifndef ONLINE_JUDGE
	time_t ed=clock()-bg;
	cout<<endl<<"time = "<<ed<<" ms"<<endl;
	fclose(stdin);fclose(stdout);
#endif
	return 0;
}
2025/4/29 19:38