4
15
2016
3

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: 3961
Small_feed 评论 (3)
1
[回复]
how to delete instag 说:
Aug 08, 2022 07:16:17 PM

Completely deleting your Instagram Account will get all your activity connection and activities through this account to be removed permanently, and also Comments, Likes, photos, Videos and your follower will be completely removed from the Instagram Account. how to delete instagram account permanently This process of deleting an Instagram Account is nowhere a recoverable process, thus if you want to get an account removed you may need to think twice and confirm, and make sure you have got the password for the Instagram Account that you want to delete from your MAC or Android, else you won’t be able to proceed further.

2
[回复]
AP Board Question Pa 说:
Aug 10, 2022 01:18:25 PM

AP Board Model Paper 2023 Class 7 Pdf Download with Answers for Telugu medium, English Medium, Hindi Medium, Urdu Medium &Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams<a href="https://www.model-paper.com/ap-board-model-paper-class-7/">AP Board Question Paper Class 7</a> AP Board Model Paper 2023 Class 7 Pdf Download with Answers for Telugu medium, English Medium, Hindi Medium, Urdu Medium &Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams

3
[回复]
boardmodelpaper.com 说:
Apr 16, 2023 06:36:32 PM

we are providing the pdf based on internet search according to past years old examination test and those question bank or study material download and shared based on the internet only.All the Users of the BoardModelPapers can use those boardmodelpaper.com sample papers or Previous Paper Pdf of class-wise study material and blueprint and any for reference purpose only and we are providing the pdf based on internet search according to past years old examination test and those question bank.


登录 *


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