【题解】10-7提高组模拟

A.[JLOI2010] 世界杯租房

lnk

由于太过强悍（题解太少），看不明白qwq，先咕着

B.《瞿葩的数字游戏》T2-多边形数

lnk

// Problem:Luogu P2674 《瞿葩的数字游戏》T2-多边形数

#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0';c=getchar();}
	return x*f;
}
int main()
{
	int t=read();
	while(t--)
	{
		int n=read();
		int cnt=0;
		if(n==1){puts("3 4");continue;}
		for(int i=3;i<=n;i++)
		{
			int tmp=1,gc=i-1;
			while(tmp<n)tmp+=gc,gc+=(i-2);
			if(tmp==n)cout<<i<<" ",cnt++;
			if(cnt==2)break;
		}
		if(cnt==0)cout<<"Poor"<<n;
		puts("");
	}
	return 0;
}

C. [BJOI2016] 回转寿司

lnk

北京省选，太过强悍（实则树状数组和线段树不熟练），先咕着

D.[USACO21OPEN] Portals G

lnk

// Problem:Luogu P7528 [USACO21OPEN] Portals G

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=100010;
int n,p[MAXN][4],f[MAXN<<1],sum;
struct node
{
	int id,cost;
}t[MAXN<<1];
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0',c=getchar();}
	return x*f;
}
bool cmp(node a,node b)
{
	return a.cost<b.cost;
}
int find(int i)
{
	if(f[i]==i)return i;
	return f[i]=find(f[i]);
}
void merge(int u,int v)
{
	f[find(v)]=find(u);
}
signed main()
{
	n=read();
	for(int i=1;i<=n*2;i++)f[i]=i;
	for(int i=1;i<=n;i++)
	{
		t[i].id=i,t[i].cost=read();
		for(int j=0;j<4;j++)p[i][j]=read();
		merge(p[i][0],p[i][1]);
		merge(p[i][2],p[i][3]);
	}
	sort(t+1,t+1+n,cmp);	
	for(int i=1;i<=n;i++)
	{
		int u=p[t[i].id][0],v=p[t[i].id][2];
		int fu=find(u),fv=find(v);
		if(fu!=fv)
		{
			sum+=t[i].cost;
			merge(u,v);
		}
	}
	cout<<sum;
	return 0;
}