4
15
2016
0

Codeforces Round #346 (Div. 2)

做个Div2还要看道题解真是没救了。。


加一加 模一模
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define INF (1<<29)
#define PII pair<int,int>
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
int n,a,b;
int main(){
	n=IN(),a=IN(),b=IN();
	OUT(((a+b-1)%n+n)%n+1);
}
对于每个地区用维护当前最大的两个就可以了
注意分数一样的情况
还有为什么这场题面都这么长啊woc
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=head[a];~x;x=next[x])
#define ll long long
#define INF (1<<29)
#define PII pair<int,int>
#define PDD pair<double,double>
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int M=100005;
int Sr[M][2],Ns,Rg,n,m;
bool Cf[M][2];
string Nm[M][2];
char ss[15];
int main(){
	n=IN(),m=IN();
	memset(Sr,-1,sizeof Sr);
	Rep(i,1,n){
		scanf("%s",ss);
		Rg=IN(),Ns=IN();
		if (Ns>Sr[Rg][0]){
			Cf[Rg][1]=Cf[Rg][0]|(Sr[Rg][0]==Sr[Rg][1]),Sr[Rg][1]=Sr[Rg][0],Nm[Rg][1]=Nm[Rg][0];
			Sr[Rg][0]=Ns,Cf[Rg][0]=0,Nm[Rg][0]=string(ss);
		}
		else if (Ns>Sr[Rg][1]) Sr[Rg][1]=Ns,Cf[Rg][1]=0,Nm[Rg][1]=string(ss);
		else if (Ns==Sr[Rg][0]) Cf[Rg][0]=1;
		else if (Ns==Sr[Rg][1]) Cf[Rg][1]=1;
	}
	Rep(i,1,m){
		if (Cf[i][0]||Cf[i][1]){puts("?");continue;}
		printf("%s %s\n",Nm[i][0].c_str(),Nm[i][1].c_str());
	}
}
直接贪心从小到大取Tanya没有的
把A排遍序用个指针扫一扫就好了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=Hd[a];~x;x=Nx[x])
#define ll long long
#define INF (1<<29)
#define PII pair<int,int>
#define PDD pair<double,double>
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=100005;
int n,m,Ans,Cur,a[N],Nw,Sq[45000];
int main(){
	n=IN(),m=IN();
	Rep(i,1,n) a[i]=IN();
	sort(a+1,a+n+1);
	Cur=Nw=1;
	while (m-Cur>=0){
		if (Nw<=n&&Cur==a[Nw]) Nw++;
		else m-=Cur,Sq[++Ans]=Cur;
		Cur++;
	}
	OUT(Ans),putchar('\n');
	Rep(i,1,Ans) OUT(Sq[i]),putchar(' ');
}
会掉到河里有四种情况:
向东走然后忽然向左转
向北走然后忽然向左转
向西走然后忽然向左转
向南走然后忽然向左转
随便判一判就好了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=Hd[a];~x;x=Nx[x])
#define ll long long
#define INF (1<<29)
#define PII pair<int,int>
#define PDD pair<double,double>
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
int n,Nx,Ny,Dr,Ans;
int main(){
	n=IN();
	Nx=IN(),Ny=IN(),Dr=0;
	Rep(i,1,n){
		int Tx=IN(),Ty=IN(),Td;
		if (Ty>Ny) Td=0;
		else if (Ty<Ny) Td=2;
		else if (Tx>Nx) Td=1;
		else Td=3;
		if ((Td+1)%4==Dr) Ans++;
		Nx=Tx,Ny=Ty,Dr=Td;
	}
	OUT(Ans);
}
首先如果一个连通块里面所有点的度数都大于1的话,
那么肯定存在一种方案使这个连通块没有独立的城市
然后只要考虑度数为1的点就可以了
我们让它连接的那条边为入边,
然后把它连接的另一个点的度数减一,
类似于拓扑排序一样做一下就可以了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Drp(x,a,b) for (int x=a;x>=b;x--)
#define Cross(x,a) for (int x=Hd[a];~x;x=Nx[x])
#define ll long long
#define INF (1<<29)
#define PII pair<int,int>
#define PDD pair<double,double>
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int M=100005;
int n,m,Cnt,To[M<<1],Nx[M<<1],Hd[M],Lt[M],Ans;
void AddEdge(int u,int v){
	To[Cnt]=v;Nx[Cnt]=Hd[u];Lt[v]++;Hd[u]=Cnt++;
}
bool Vs[M];
queue<int>Q;
int main(){
	n=IN(),m=IN();
	memset(Hd,-1,sizeof Hd);
	Rep(i,1,m){
		int u=IN(),v=IN();
		AddEdge(u,v),AddEdge(v,u);
	}
	Rep(i,1,n) if (Lt[i]==1) Q.push(i);
	while (!Q.empty()){
		int u=Q.front();Q.pop();
		Vs[u]=1;
		Cross(i,u){
			int v=To[i];
			if (Vs[v]) continue;
			Lt[v]--;
			if (Lt[v]==1) Q.push(v);
		}
	}
	Rep(i,1,n) if (!Lt[i]) Ans++;
	OUT(Ans);
}
题目就是要找一个连通块,
使得它的点数乘以它里面的点的最小权值等于 $k$
这题我特么一直在想怎么构图然后跑一跑。。
然后看了题解发现好傻逼。。
把所有点从大到小排一遍序
然后处理当前点的时候把它和它周围的之前处理过的点
用并查集并到一起
因为是从小到大,所以这个集合里面权值最小的点肯定是它
然后如果它的权值是 $k$ 的因数,就判断一下集合大小
如果大于等于需要的点数的话直接DFS一下输出就可以了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=(int)b;x++)
#define Drp(x,a,b) for (int x=a;x>=(int)b;x--)
#define Cross(x,a) for (int x=Hd[a];~x;x=Nx[x])
#define ll long long
#define INF (1<<29)
#define PII pair<int,int>
#define PDD pair<double,double>
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
const int N=1005;
int n,m,Fa[N*N],Sz[N*N],Mp[N][N],Mn;
ll S,Nd;
struct Node{
	int Ps,Ky;
	bool operator <(const Node&x)const{return Ky>x.Ky;}
}a[N*N];
int GetFa(int x){
	if (Fa[x]==x||!Fa[x]) return Fa[x];
	return Fa[x]=GetFa(Fa[x]);
}
bool Vs[N][N];
void Dfs(int x,int y){
	if (!Nd) return;
	Vs[x][y]=1,Nd--;
	if (!Nd) return;
	if (x>1&&Mp[x-1][y]>=Mn&&!Vs[x-1][y]) Dfs(x-1,y);
	if (x<n&&Mp[x+1][y]>=Mn&&!Vs[x+1][y]) Dfs(x+1,y);
	if (y>1&&Mp[x][y-1]>=Mn&&!Vs[x][y-1]) Dfs(x,y-1);
	if (y<m&&Mp[x][y+1]>=Mn&&!Vs[x][y+1]) Dfs(x,y+1);
}
int main(){
	n=IN(),m=IN(),S=IN();
	Rep(i,1,n) Rep(j,1,m){
		Mp[i][j]=IN();
		int ID=(i-1)*m+j;
		a[ID].Ky=Mp[i][j],a[ID].Ps=ID;
	}
	sort(a+1,a+n*m+1);
	Rep(i,1,n*m){
		Fa[a[i].Ps]=a[i].Ps,Sz[a[i].Ps]=1;
		int Ps=a[i].Ps,x=(Ps-1)/m+1,y=(Ps-1)%m+1,F;
		if (x>1&&(F=GetFa(Ps-m))&&F!=Ps) Fa[F]=Ps,Sz[Ps]+=Sz[F];
		if (x<n&&(F=GetFa(Ps+m))&&F!=Ps) Fa[F]=Ps,Sz[Ps]+=Sz[F];
		if (y>1&&(F=GetFa(Ps-1))&&F!=Ps) Fa[F]=Ps,Sz[Ps]+=Sz[F];
		if (y<m&&(F=GetFa(Ps+1))&&F!=Ps) Fa[F]=Ps,Sz[Ps]+=Sz[F];
		if (S%a[i].Ky==0){
			Nd=S/a[i].Ky,Mn=a[i].Ky;
			if (Sz[a[i].Ps]>=Nd){
				puts("YES");
				Dfs(x,y);
				Rep(x,1,n){
					Rep(y,1,m) if (Vs[x][y]) printf("%d ",a[i].Ky);
						else printf("0 ");
					puts("");
				}
				return 0;
			}
		}
	}
	puts("NO");
}
因为只能取顶上的,
所以 $F_{i,j}$ 表示只拿第 $i$ 列且之前的,
且强制第 $i$ 列从顶上拿到高度为 $j$ 的地方的方案数。
考虑现在处理第 $i$ 列,(因为最后一格不能拿所以首先高度减一)
如果 $h_i\ge h_{i-1}$ 的话,因为要连通
所以 $F_{i,h_{i-1}+1}\sim F_{i,h_i}$ 全都是1
然后 $F_{i,1}\sim F_{i,h_{i-1}}$ 全都等于 $\sum_{j=1}^{h_{i-1}}{F_{i-1,j}}$
否则如果 $h_i\lt h_{i-1}$的话,
$F_{i,1}\sim F_{i,h_i}$ 全都等于 $\sum_{j=1}^{h_i}{F_{i-1,j}}$
然后就会发现每列的$ F_{i,j} $最多分成两段,下面一段值全都一样,上面都是1
然后记录一下下面一段的高度和值,随便搞一搞就行了
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<bitset>
#include<vector>
#define Rep(x,a,b) for (int x=a;x<=(int)b;x++)
#define Drp(x,a,b) for (int x=a;x>=(int)b;x--)
#define Cross(x,a) for (int x=Hd[a];~x;x=Nx[x])
#define ll long long
#define INF (1<<29)
#define PII pair<int,int>
#define PDD pair<double,double>
#define mk(a,b) make_pair(a,b)
#define fr first
#define sc second
#define MOD 1000000007
using namespace std;
inline ll IN(){
	ll x=0;int ch=getchar(),f=1;
	while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
	if (ch=='-'){f=-1;ch=getchar();}
	while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
inline void OUT(ll x){
	if (x<0) putchar('-'),x=-x;
	if (x>=10) OUT(x/10),putchar(x%10+'0');
		else putchar(x+'0');
}
ll Ans,Vl,Ht,Lst;
int n;
int main(){
	n=IN();
	Ans=Lst=IN()-1;
	Rep(i,2,n){
		ll Nw=IN()-1;
		if (Nw>Lst){
			Vl=(Ht*Vl+Lst-Ht+1)%MOD;
			Ht=Lst;
		}
		else{
			if (Nw>=Ht) Vl=(Nw-Ht+Ht*Vl+1)%MOD;
			else Vl=(Nw*Vl+1)%MOD;
			Ht=Nw;
		}
		(Ans+=Ht*Vl+(Nw-Ht))%=MOD;
		Lst=Nw;
	}
	OUT(Ans);
}

 

Category: Codeforces | Tags: 模拟 贪心 特判 DP 拓扑排序 图论 | Read Count: 333

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com