4
12
2016
0

Codeforces Round #296

第528场肯定是要去做一做的

就按照GCD那样子搞一搞,中间答案累加一下就好了
#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');
}
ll Ans;
void Solve(ll a,ll b){
	if (b==0) return;
	Ans+=a/b;
	Solve(b,a%b);
}
int main(){
	Solve(IN(),IN());
	OUT(Ans);
}
我是把每对字符的出现位置都存了一下,
然后先找有没有 $(i,j)和(j,i) (i\ne j)$ 都出现过的,
有就直接交换,输出 $Cnt-2$
否则就找一下有没有 $(i,j)和(j,k) (i\ne j\ne k)$,
有的话也换一下,输出 $Cnt-1$
否则直接输出 $Cnt$
#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 N=200005;
int n;
char S[N],T[N];
int Ps[30][30];
int main(){
	n=IN();
	scanf("%s%s",S+1,T+1);
	int Ans=0;
	Rep(i,1,n){
		Ps[S[i]-'a'][T[i]-'a']=i;
		if (S[i]!=T[i]) Ans++;
	}
	Rep(i,0,25) Rep(j,i+1,25){
		if (Ps[i][j]&&Ps[j][i]){
			printf("%d\n%d %d\n",Ans-2,Ps[i][j],Ps[j][i]);
			return 0;
		}
	}
	Rep(i,0,25) Rep(j,0,25){
		if (i==j||!Ps[i][j]) continue;
		Rep(k,0,25){
			if (j==k||!Ps[j][k]) continue;
			printf("%d\n%d %d\n",Ans-1,Ps[i][j],Ps[j][k]);
			return 0;
		}
	}
	printf("%d\n",Ans);
	puts("-1 -1");
}
这题可以把行和列分开来考虑
然后以行为例
我用了两个set,一个记录修改,一个记录每段的长度
然后修改的时候我们把它的前驱和后缀都拎出来,
就能知道切的这一段长度是多少
然后把这一段拎出来切断再放进去
再把这次修改放到管修改的那个set里
输出的时候输出行最大值和列最大值的乘积就好了
#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');
}
multiset<int>Hor,Ver,Mdh,Mdv;
int w,h,n,x;
char opt[2];
int main(){
	w=IN(),h=IN(),n=IN();
	Hor.insert(h),Ver.insert(w);
	Mdh.insert(1),Mdh.insert(h+1);
	Mdv.insert(1),Mdv.insert(w+1);
	Rep(i,1,n){
		scanf("%s",opt);
		x=IN()+1;
		if (opt[0]=='H'){
			multiset<int>::iterator it=Mdh.lower_bound(x);
			int Mx=*it,Mn=*--it,L=Mx-Mn;
			Mdh.insert(x);
			Hor.erase(Hor.find(L));
			Hor.insert(x-Mn),Hor.insert(Mx-x);
			OUT(1ll*(*--Hor.end())*(*--Ver.end())),putchar('\n');
		}
		else{
			multiset<int>::iterator it=Mdv.lower_bound(x);
			int Mx=*it,Mn=*--it,L=Mx-Mn;
			Mdv.insert(x); 
			Ver.erase(Ver.find(L));
			Ver.insert(x-Mn),Ver.insert(Mx-x);
			OUT(1ll*(*--Hor.end())*(*--Ver.end())),putchar('\n'); 
		}
	}
} 
两个点之间连点的条件是它们之间的距离大于它们的权值之和
很容易想到把一个点看成一条线段,
然后题意就变成了选尽量多的线段并使它们不相交
排序以后随便搞一搞就好了
#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');
}
const int N=200005;
struct Seg{
	int l,r;
	bool operator <(const Seg&x)const{return l<x.l;}
}a[N];
int n,Ls[N<<1],Lc,Ks,F[N<<1];
map<int,int>Li;
int main(){
	n=IN();
	Rep(i,1,n){
		int x=IN(),w=IN();
		a[i].l=x-w;a[i].r=x+w;
		Ls[++Lc]=a[i].l,Ls[++Lc]=a[i].r;
	}
	sort(Ls+1,Ls+Lc+1);
	Li[Ls[1]]=++Ks;
	Rep(i,2,Lc) if (Ls[i]!=Ls[i-1]) Li[Ls[i]]=++Ks;
	Rep(i,1,n){a[i].l=Li[a[i].l];a[i].r=Li[a[i].r];}
	sort(a+1,a+n+1);
	int Ans=0,Nw=1;
	Rep(i,1,Ks){
		Ans=max(Ans,F[i]);
		while (Nw<=n&&a[Nw].l==i){
			F[a[Nw].r]=max(F[a[Nw].r],Ans+1);
			Nw++;
		}
	}
	OUT(Ans);
}
题意就是让所有的点出度和入度都是偶数
首先不管方向,把度数为奇数的点之间随便连一下边
然后跑欧拉回路,如果边数是偶数,那就这么连:
$A->B<-C->D<-E...<-A$
如果是奇数的话,先给 $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=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');
}
const int N=100005,M=200005;
int to[M*2+N],next[M*2+N],head[N],vis[M*2+N],cnt;
void AddEdge(int u,int v){
	to[cnt]=v;next[cnt]=head[u];head[u]=cnt++;
}
int n,m,Lt[N],As[M<<2][2],Ans,Eu[M*2+N],v;
void DFS(int u){
	for (int &i=head[u];~i;){
		if (vis[i]){i=next[i];continue;}
		int v=to[i];
		vis[i]=vis[i^1]=1;
		i=next[i];
		DFS(v);
	}
	Eu[++v]=u;
}
int main(){
	n=IN(),m=IN();
	memset(head,-1,sizeof head);
	Rep(i,1,m){
		int u=IN(),v=IN();
		AddEdge(u,v);AddEdge(v,u);
		Lt[u]++,Lt[v]++;
	}
	int Lst=0;
	Rep(i,1,n) if (Lt[i]&1){
		if (!Lst) Lst=i;
		else AddEdge(Lst,i),AddEdge(i,Lst),Lst=0; 
	}
	Ans=0;
	Rep(u,1,n){
		Cross(i,u){
			if (vis[i]) continue;
			v=0;
			DFS(u);
			if (!(v&1)){
				As[++Ans][0]=Eu[1];
				As[Ans][1]=Eu[1];
			}
			Rep(j,1,v-1){
				if (j&1) As[++Ans][0]=Eu[j],As[Ans][1]=Eu[j+1];
					else As[++Ans][0]=Eu[j+1],As[Ans][1]=Eu[j];
			}
		}
	}
	OUT(Ans),putchar('\n');
	Rep(i,1,Ans){
		OUT(As[i][0]),putchar(' '),OUT(As[i][1]),putchar('\n');
	}
}
标算好像是FFT hhh
然而可以用 Bitset 使过去
把 $A.T.G.C$ 分开考虑,
然后就可以搞成01的形式
随便搞一下就好了 不懂可以留言
#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');
}
const int N=200005;
int n,m,k,Nw,Tmp[N];
char S[N],P[N];
bitset<N>Ex[4],Ans;
int main(){
	n=IN(),m=IN(),k=IN();
	scanf("%s%s",S,P);
	Rep(i,0,n-1){
		if (S[i]=='A') S[i]=0;if (S[i]=='T') S[i]=1;
		if (S[i]=='G') S[i]=2;if (S[i]=='C') S[i]=3;
	}
	Rep(i,0,m-1){
		if (P[i]=='A') P[i]=0;if (P[i]=='T') P[i]=1;
		if (P[i]=='G') P[i]=2;if (P[i]=='C') P[i]=3;
	}
	Rep(Lt,0,3){
		memset(Tmp,0,sizeof Tmp);
		Rep(i,0,n-1) if (S[i]==Lt) Tmp[max(0,i-k)]++,Tmp[min(n,i+k+1)]--;
		Nw=0;Rep(i,0,n-1) Nw+=Tmp[i],Ex[Lt][i]=Nw?1:0;
	}
	Rep(i,0,n-m) Ans[i]=1;
	Rep(i,0,m-1) Ans&=Ex[P[i]]>>i;
	int Cnt=0;
	Rep(i,0,n-m) Cnt+=(int)Ans[i];
	OUT(Cnt);
}
官方题解是$n^2logn$
然后民间一大堆 $n^2$ 的
我随便找了一个看了一下
简单来说就是,三角形ABC的面积等于:
$\frac{A\times B+B\times C+C\times A}{2} (\times 是叉积)$
然后就考虑每两个交点连成的边对于答案的贡献
是两个点的叉积乘以$\frac{1}{2*总三角形个数}$
为什么分母要乘二呢?因为三角形面积要除二233
但是直接算的话是$n^3$的
然后就考虑一条直线上所有的交点的贡献
因为 $A\times B+A\times C=A\times (B+C)$
所以前缀和搞一下就可以了
然而因为算叉积的时候,
要么所有三角形都顺时针算,要么都逆时针
所以为了防止乱算,我们把所有直线按斜率排序
大家可以自己手画一下,这样能保证都是同一方向
然后枚举直线之后,
按顺序把它其它直线与它的交点顺序加进去,
算一下贡献, 再加到前缀和里面
好了 其实我知道你们都没有看懂0.0
#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 N=3005;
struct Point{
	double a,b,c,ang;
	bool operator <(const Point&x)const{return ang>x.ang;}
}p[N];
PDD Intersec(Point a,Point b){
	double Tmp=b.a*a.b-a.a*b.b;
	double x=(b.c*a.b-a.c*b.b)/Tmp;
	double y=(a.c*b.a-b.c*a.a)/Tmp;
	return mk(x,y);
}
double cross(PDD a,PDD b){
	return a.fr*b.sc-a.sc*b.fr;
}
int n;
int main(){
	n=IN();
	Rep(i,1,n){
		p[i].a=IN(),p[i].b=IN(),p[i].c=IN();
		if (p[i].a>0) p[i].a=-p[i].a,p[i].b=-p[i].b,p[i].c=-p[i].c;
	}
	Rep(i,1,n) p[i].ang=atan2(-p[i].a,p[i].b);
	sort(p+1,p+n+1);
	double Ans=0,Pb=3.0/n/(n-1)/(n-2);
	Rep(i,1,n){
		PDD Pre=mk(0,0);
		Rep(j,1,n-1){
			int k=(i+j-1)%n+1;
			PDD Cur=Intersec(p[i],p[k]);
			Ans+=Pb*cross(Cur,Pre);
			Pre.fr+=Cur.fr,Pre.sc+=Cur.sc;
		}
	}
	printf("%.10lf\n",Ans);
}

 

Category: Codeforces | Tags: 字符串 DP 计算几何 模拟 STL | Read Count: 264

登录 *


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