BUPT2017 wintertraining(15) #1 题解

#include<cstdio>
long long a,b,c;
int main() {
	scanf("%lld%lld%lld",&a,&b,&c);
	if(c==0&&b==a||c&&(b-a)%c==0&&(b-a)/c>=0)puts("YES");
	else puts("NO");
	return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#define ll long long
#define N 305
using namespace std;
int s,m,r,g[N][N];
int cnt,le[N],re[N];
int dp[N][N];
bool vis[2][N];
void dfs(int v,int c){
	vis[c][v]=1;
	if(c)le[cnt]++;else re[cnt]++;//连通图左边、右边的点个数
	for(int i=1;i<=m;i++)//c==1，左边走到右边
		if((c&&g[v][i]||!c&&g[i][v])&&!vis[!c][i]) dfs(i,!c);
}
int main() {
	scanf("%d",&s);
	for(int cas=1;cas<=s;cas++){
		for(int i=0;i<N;i++)le[i]=re[i]=vis[0][i]=vis[1][i]=0;
		memset(g,0,sizeof g);
		memset(dp,0,sizeof dp);
		cnt=0;
		scanf("%d%d",&m,&r);
		for(int i=1;i<=r;i++){
			int x,y;
			scanf("%d%d",&x,&y);
			g[x][y]=1;
		}
		for(int i=1;i<=m;i++)
		for(int c=0;c<2;c++)
			if(!vis[c][i]){
				cnt++;
				dfs(i,c);
			}
		dp[0][0]=1;
		for(int i=1;i<=cnt;i++)
		for(int j=m/2;j>=le[i];j--)
		for(int k=m/2;k>=re[i];k--)
			dp[j][k]|=dp[j-le[i]][k-re[i]];

		int i=m/2;
		while(i&&dp[i][i]==0)i--;
		printf("%d\n",i);
	}
	return 0;
}

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
#define N 1005
#define M 2000005
#define INF 0x7fffffff
struct edge{
	int to,next,w;
}e[M];
int head[N],g[N],cnt;
int d[N],ans,tans;
int st,ed;
void add(int u,int v,int w){
	e[cnt]=(edge){v,head[u],w};head[u]=cnt++;
	e[cnt]=(edge){u,head[v],0};head[v]=cnt++;//反向弧
}
int bfs(){
	memset(d,-1,sizeof d);
	queue<int>q;
	q.push(st);
	d[st]=0;
	while(!q.empty()){
		int i,k=q.front();
		q.pop();
		for(i=head[k];~i;i=e[i].next){
			int v=e[i].to;
			if(e[i].w>0&&d[v]==-1){
				d[v]=d[k]+1;
				q.push(v);
			}
		}
	}
	return d[ed]>0;
}
int dinic(int k,int low){//在k节点有流量low，到终点ed的最大流
	if(k==ed||low==0)return low;
	int a,res=0;
	for(int &i=g[k];~i;i=e[i].next){//这个g就是当前弧优化
		int v=e[i].to;
		if(d[v]==d[k]+1&&e[i].w>0&&(a=dinic(v,min(low,e[i].w)))){
			res+=a;//当前这条弧送了a流量到终点
			low-=a;
			e[i].w-=a;
			e[i^1].w+=a;
			if(!low) break;//如果k相连的前面几条弧已经把low那么多流量送到终点，就不需要后面的弧了，下次访问k时就从现在的g[k]这条弧开始增广。
		}
	}
	return res;
}
void solve(){
    ans = 0;
    while(bfs()) {
    	memcpy(g,head,sizeof g);//重新计算过层次图后再初始化当前弧g
    	while(tans=dinic(st, INF)) ans += tans;
	}
}
void init(){
	cnt=0;
	memset(head, -1, sizeof head);
}
int p[N],s[N],ee[N];
int main(){
	int t;
	scanf("%d",&t);
	for(int cas=1;cas<=t;cas++){
		printf("Case %d: ",cas);
		int n,m;
		int pans=0;
		init();
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++){
			scanf("%d%d%d",&p[i],&s[i],&ee[i]);
			add(st,i,p[i]);
			pans+=p[i];
			for(int j=s[i];j<=ee[i];j++)
				add(i,j+n,1);
		}
		ed=n+501;
		for(int i=n+1;i<=n+500;i++){
			add(i,ed,m);
		}
		solve();
		if(ans==pans)puts("Yes\n");
		else puts("No\n");
	}
}

#include<cstdio>
#include<cstring>
#define ll long long
#define N 100005
const ll M = 1e9+7;
using namespace std;
struct Mat{
	ll a[2][2];
	Mat operator + (const Mat &B){
		Mat C;
		C.a[0][0]=(a[0][0]+B.a[0][0])%M;
		C.a[0][1]=(a[0][1]+B.a[0][1])%M;
		C.a[1][0]=(a[1][0]+B.a[1][0])%M;
		C.a[1][1]=(a[1][1]+B.a[1][1])%M;
		return C;
	}
	Mat operator * (const Mat &B){
		Mat C;
		C.a[0][0]=(a[0][0]*B.a[0][0]+a[0][1]*B.a[1][0])%M;
		C.a[0][1]=(a[0][0]*B.a[1][0]+a[0][1]*B.a[1][1])%M;
		C.a[1][0]=(a[1][0]*B.a[0][0]+a[1][1]*B.a[1][0])%M;
		C.a[1][1]=(a[1][0]*B.a[1][0]+a[1][1]*B.a[1][1])%M;
		return C;
	}
}e={1,0,0,1},b={0,1,1,1},bv,tr[N<<2],lz[N<<2];
Mat pow (int t){
	Mat C=e,A=b;
	while(t){
		if(t&1)C=C*A;
		A=A*A;
		t>>=1;
	}
	return C;
}
int L[N<<2],R[N<<2];
void pushDown(int x){
	tr[x<<1]  =tr[x<<1]  *lz[x];
	tr[x<<1|1]=tr[x<<1|1]*lz[x];
	lz[x<<1]  =lz[x<<1]  *lz[x];
	lz[x<<1|1]=lz[x<<1|1]*lz[x];
	lz[x]=e;
}
void pushUp(int x){
	tr[x]=tr[x<<1]+tr[x<<1|1];
}
void build(int l,int r,int x){
	L[x]=l;R[x]=r;
	lz[x]=e;
	if(l==r){
		int a;
		scanf("%d",&a);
		tr[x]=pow(a-1);
		return;
	}
	int m=l+r>>1;
	build(l,m,x<<1);
	build(m+1,r,x<<1|1);
	pushUp(x);
}
void add(int l,int r,int x,int v){
	if(l<=L[x]&&r>=R[x]){
		tr[x]=tr[x]*bv;
		lz[x]=lz[x]*bv;
		return;
	}
	if(L[x]!=R[x])pushDown(x);
	if(l<=R[x<<1])add(l,r,x<<1,v);
	if(r>R[x<<1])add(l,r,x<<1|1,v);
	pushUp(x);
}
ll query(int l,int r,int x){
	if(l>R[x]||r<L[x])return 0;
	if(l<=L[x]&&r>=R[x])return tr[x].a[1][1];
	if(L[x]!=R[x])pushDown(x);
	return (query(l,r,x<<1)+query(l,r,x<<1|1))%M;
}
int main() {
	int n,m,l,r,x,op;
	scanf("%d %d",&n,&m);
	build(1,n,1);
	for(int i=1;i<=m;i++){
		scanf("%d %d %d",&op, &l, &r);
		if(op==1) scanf("%d",&x), bv=pow(x), add(l,r,1,x);
		else printf("%lld\n",query(l,r,1));
	}
	return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
const int N=1e5+5;
const ll M=1e9+7;
const ll inv2=5e8+4;
using namespace std;

struct Num{
	ll a,b;
	Num():a(1),b(0){}
	Num(ll x,ll y):a(x%M),b(y%M){}
	Num operator +(const Num &B)const{
		return Num(a+B.a,b+B.b);
	}
	Num operator *(const Num &B)const{
		return Num(a*B.a+b*B.b*5,a*B.b+b*B.a);
	}
	Num operator ^(int t)const{
		Num A=(*this),B(1,0);
		while(t){if(t&1)B=B*A;A=A*A;t>>=1;}
		return B;
	}
}eA(inv2,inv2),eB(inv2,-inv2),tr[2][N<<2],lz[2][N<<2];

void pushup(int i,int x){
	tr[i][x]=tr[i][x<<1]+tr[i][x<<1|1];
}
void pushdown(int i,int x){
	tr[i][x<<1]=tr[i][x<<1]*lz[i][x];
	tr[i][x<<1|1]=tr[i][x<<1|1]*lz[i][x];
	lz[i][x<<1]=lz[i][x<<1]*lz[i][x];
	lz[i][x<<1|1]=lz[i][x<<1|1]*lz[i][x];
	lz[i][x].a=1,lz[i][x].b=0;
}

#define ls l,r,L,L+R>>1,x<<1
#define rs l,r,(L+R>>1)+1,R,x<<1|1

void add(int l,int r,int L,int R,int x,int i,Num ad){
	if(l>R||L>r)return;
	if(l<=L&&R<=r){
		tr[i][x]=tr[i][x]*ad;
		lz[i][x]=lz[i][x]*ad;
		return;
	}
	if(L!=R) pushdown(i,x);
	add(ls,i,ad);add(rs,i,ad);
	pushup(i,x);
}
ll query(int l,int r,int L,int R,int x){
	if(l>R||L>r)return 0;
	if(l<=L&&R<=r)return (tr[0][x].b-tr[1][x].b)%M;
	if(L!=R)pushdown(0,x),pushdown(1,x);
	return (query(ls)+query(rs))%M;
}

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1,a;i<=n;i++){
		scanf("%d",&a);
		add(i,i,1,n,1,0,eA^a);
		add(i,i,1,n,1,1,eB^a);
	}
	for(int i=1,t,l,r,x;i<=m;i++){
		scanf("%d%d%d",&t,&l,&r);
		if(t==1){
			scanf("%d",&x);
			add(l,r,1,n,1,0,eA^x);
			add(l,r,1,n,1,1,eB^x);
		}
		else printf("%lld\n",query(l,r,1,n,1));
	}
	return 0;
}

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
#define ll long long
#define N 300005
const ll INF = 1LL << 61;
using namespace std;

int t[N],r[N],empty[N];
ll ans[N];
struct Point{
	ll x,y;
	bool operator <(const Point &B)const{
		return x<B.x||(x==B.x&&y<B.y);
	}
	Point operator -(const Point &B)const{
		return (Point){x-B.x,y-B.y};
	}
	Point operator +(const Point &B)const{
		return (Point){x+B.x,y+B.y};
	}
	ll operator ^(const Point &B)const{
		return x*B.y-y*B.x;
	}
	ll operator *(const Point &B)const{
		return x*B.x+y*B.y;
	}
}p[N],S[N];

vector<Point> tr[N<<2];
void insert(int l,int r,int L,int R,int o,int v){
	if(l<=L&&R<=r){
		tr[o].push_back(p[v]);
		return;
	}
	int M=L+R>>1;
	if(l<=M)insert(l,r,L,M,o<<1,v);
	if(r>M)insert(l,r,M+1,R,o<<1|1,v);
}
void query(int x,int n){
	int l=1,r=n;
	while(r-l>=3){//三分求最大值
		int m1=l+(r-l)/3;
		int m2=l+(r-l)*2/3;
		if(p[x]*S[m1]<p[x]*S[m2])l=m1;
		else r=m2;
	}
	for(int i=l;i<=r;i++)
		ans[x]=max(ans[x],p[x]*S[i]);
}

void solve(int l,int r,int o){
	if(l<r){
		int m=l+r>>1;
		solve(l,m,o<<1);
		solve(m+1,r,o<<1|1);
	}
	sort(tr[o].begin(),tr[o].end());
	int top=0;
	for(int i=0;i<tr[o].size();i++){
		while(top>1&&((S[top]-S[top-1])^(tr[o][i]-S[top]))>=0)top--;
		S[++top]=tr[o][i];
	}
	for(int i=l;i<=r;i++) if(t[i]==3&&!empty[i]) query(i,top);
}

int main() {
	int n;
	scanf("%d",&n);
	for(int i=1,cnt=0,x;i<=n;i++){
		scanf("%d",&t[i]);
		if(t[i]==1)
			scanf("%lld %lld",&p[i].x,&p[i].y), r[i]=n, cnt++;
		else if(t[i]==2)
			scanf("%d",&x), r[x]=i, cnt--;
		else
			scanf("%lld",&p[i].x), p[i].y=1LL, empty[i]=(cnt==0), ans[i]=-INF;
	}
	
	for(int i=1;i<=n;i++)if(t[i]==1&&i+1<=r[i]) insert(i,r[i],1,n,1,i);

	solve(1,n,1);

	for(int i=1;i<=n;i++)if(t[i]==3){
		if(empty[i]) puts("EMPTY SET");
		else printf("%lld\n",ans[i]);
	}
	return 0;
}

#include<cstdio>
#include<cmath>
#define pi acos(-1.0)
using namespace std;
double d,h,v,e;
int main() {
	scanf("%lf%lf%lf%lf",&d,&h,&v,&e);
	double s=v/pi/(d/2)/(d/2)-e;
	if(s>0)printf("YES\n%f",h/s);
	else puts("NO");
	return 0;
}

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define ll long long
#define N 100005
using namespace std;
struct star{
	ll x,y;int id;
}s[N];
int n;
int cmp(star a,star b){
	return a.x<b.x||a.x==b.x&&a.y<b.y;
}
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld%lld",&s[i].x,&s[i].y);
		s[i].id=i;
	}
	sort(s+1,s+1+n,cmp);
	printf("%d %d ",s[1].id,s[2].id);
		for(int i=3;i<=n;i++){
			if((s[1].x-s[2].x)*(s[2].y-s[i].y)!=(s[1].y-s[2].y)*(s[2].x-s[i].x)){
				printf("%d",s[i].id);break;
			}
		}
	return 0;
}