2
10
2017
0

395

 

Div2.A

#include <stdio.h>
inline int F() { register int aa , bb , ch;
	while(ch = getchar() , (ch<'0'||ch>'9') && ch!='-'); ch == '-' ? aa=bb=0 : (aa=ch-'0',bb=1);
	while(ch = getchar() , ch>='0'&&ch<='9') aa = aa*10 + ch-'0'; return bb ? aa : -aa;
}
int gcd(int a , int b) { return b ? gcd(b,a%b) : a; }
int main() {
	int n = F() , m = F() , k = F();
	int lcm = n*m/gcd(n,m);
	printf("%d\n",k/lcm);
}

Div2.B

#include <stdio.h>
#include <iostream>
using std::swap;
inline int F() { register int aa , bb , ch;
	while(ch = getchar() , (ch<'0'||ch>'9') && ch!='-'); ch == '-' ? aa=bb=0 : (aa=ch-'0',bb=1);
	while(ch = getchar() , ch>='0'&&ch<='9') aa = aa*10 + ch-'0'; return bb ? aa : -aa;
}
const int Maxn = 200005;
int n , a[Maxn];
int main() {
	int n = F();
	for(int i=1; i<=n; ++i) a[i] = F();
	for(int i=1; i+i<=n; ++i) if(i&1) swap(a[i],a[n-i+1]);
	for(int i=1; i<=n; ++i) printf("%d ",a[i]);
}

A.

#include <stdio.h>
inline int F() { register int aa , bb , ch;
	while(ch = getchar() , (ch<'0'||ch>'9') && ch != '-'); ch == '-' ? aa=bb=0 : (aa=ch-'0',bb=1);
	while(ch = getchar() , ch>='0'&&ch<='9') aa = aa*10 + ch-'0'; return bb ? aa : -aa;
}
const int Maxn = 100005;
const int Maxm = 2*Maxn;
int n , son[Maxn] , up[Maxn] , fa[Maxn] , col[Maxn] , ans;
int to[Maxm] , next[Maxm] , g[Maxn] , ecnt = 0;
void ins(int a , int b) { to[++ecnt] = b; next[ecnt] = g[a]; g[a] = ecnt; }
void dfs1(int x) {
	for(int i=g[x]; i; i=next[i]) {
		if(to[i] == fa[x]) continue;
		fa[to[i]] = x;
		dfs1(to[i]);
		if(son[x] == -1) continue;
		if(col[x] != col[to[i]] || son[to[i]]) {
			if(son[x]) son[x] = -1;
			else son[x] = to[i];
		}
	}
}
void dfs2(int x , int y) {
	int flag = 0;
	for(int i=g[x]; i; i=next[i]) {
		if(to[i] == fa[x]) continue;
		if(son[to[i]]) {
			flag = 1; break;
		}
	}
	if(!flag) { ans = x; return; }
	if(son[x] == -1 || y) return;
	if(son[x]) {
		if(col[son[x]] == col[x]) dfs2(son[x],0);
		else dfs2(son[x],1);
		return;
	}
}
int main() {
	n = F();
	for(int i=1; i<n; ++i) {
		int a = F() , b = F();
		ins(a,b); ins(b,a);
	}
	for(int i=1; i<=n; ++i) col[i] = F();
	dfs1(1); dfs2(1,0);
	if(ans) { puts("YES"); printf("%d\n",ans); }
	else puts("NO");
}

B.

#include <stdio.h>
inline int F() { register int aa , bb , ch;
	while(ch = getchar() , (ch<'0'||ch>'9') && ch != '-'); ch == '-' ? aa=bb=0 : (aa=ch-'0',bb=1);
	while(ch = getchar() , ch>='0'&&ch<='9') aa = aa*10 + ch-'0'; return bb ? aa : -aa;
}
int main() {
	int n = F(); puts("YES");
	for(int i=1; i<=n; ++i) {
		int a = F() , b = F() , c = F() , d = F();
		a = (a%2+2)%2; b = (b%2+2)%2;
		printf("%d\n",1+a+a+b);
	}
}

C.

 

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
inline int F() { register int aa , bb , ch;
	while(ch = getchar() , (ch<'0'||ch>'9') && ch != '-'); ch == '-' ? aa=bb=0 : (aa=ch-'0',bb=1);
	while(ch = getchar() , ch>='0'&&ch<='9') aa = aa*10 + ch-'0'; return bb ? aa : -aa;
}
const int Maxn = 100005;
int n , m , ans = -1 , ansd , a[Maxn] , b[Maxn];
int Pow(int a , int b) {
	int ans = 1;
	for(; b; b>>=1 , a = (long long)a*a % m) if(b&1) ans = (long long)ans * a % m;
	return ans;
}
inline int find(int *a , int n , int x) { return *lower_bound(a+1,a+n+1,x) == x; }
void sol(int *a , int n) {
	if(n == 1) { ans = a[1] , ansd = 1; return; }

	int tmp = a[2] - a[1] , cnt = 0;
	for(int i=1; i<=n; ++i)
		if(find(a,n,(a[i]+tmp)%m))
			++cnt;
	ansd = (long long)tmp * Pow(n-cnt,m-2) % m;
	int d = (m - ansd) % m;
	for(int i=1; i<=n; ++i) {
		if(!find(a,n,(a[i]+d)%m)) {
			if(ans == -1) ans = a[i];
			else { ans = -1; return; }
		}
	}
}
int main() {
	m = F() , n = F();
	for(int i=1; i<=n; ++i) a[i] = F();
	sort(a+1,a+n+1);
	if(n == 1 || n == m) { printf("%d 1\n",a[1]); return 0; }
	if(n+n < m) sol(a,n);
	else {
		int top = 0;
		for(int i=0; i<m; ++i)
			if(!find(a,n,i)) b[++top] = i;
		sol(b,top);
		if(ans != -1) ans = (ans + (long long)ansd * top) % m;
	}
	if(ans == -1) printf("%d\n",ans);
	else printf("%d %d\n",ans,ansd);
}

D.

#include <stdio.h>
#include <map>
#include <algorithm>
#include <iostream>
using std::min; using std::max;
inline int F() { register int aa , bb , ch;
	while(ch = getchar() , (ch<'0'||ch>'9') && ch != '-'); ch == '-' ? aa=bb=0 : (aa=ch-'0',bb=1);
	while(ch = getchar() , ch>='0'&&ch<='9') aa = aa*10 + ch-'0'; return bb ? aa : -aa;
}
const int Maxn = 200005;
const int Maxm = 2*Maxn;
int n , rt = 0 , ans = 0 , sans = 0 , sum = 0 , fa[Maxn] , size[Maxn] , f[Maxn] , Ha[Maxn] , H[Maxn];
//fa:父亲 size:子树大小 f:最大子树大小 Ha:由trie树得到的哈希值 H:Ha出现次数
int	len = 0 , a[Maxn];
int to[Maxm] , next[Maxm] , g[Maxn] , ecnt = 0;
inline void ins(const int&a , const int&b) {
	to[++ecnt] = b; next[ecnt] = g[a]; g[a] = ecnt;
	to[++ecnt] = a; next[ecnt] = g[b]; g[b] = ecnt;
}
namespace Trie {
	int sz = 1;
	std::map<int,int> c[Maxn];
	int insert() {
		int now = 1;
		for(int i=1; i<=len; ++i) {
			if(!c[now][a[i]]) c[now][a[i]] = ++sz;
			now = c[now][a[i]];
		} return now;
	}
}
void modify(int x , int val) {
	if(H[x]) --sum;
	H[x] += val;
	if(H[x]) ++sum;
}
void getrt(int x) {
	size[x] = 1;
	for(int i=g[x]; i; i=next[i]) {
		if(to[i] == fa[x]) continue;
		fa[to[i]] = x;
		getrt(to[i]);
		size[x] += size[to[i]];
		if(size[to[i]] > f[x]) f[x] = size[to[i]];
	}
	if(n-size[x] > f[x]) f[x] = n-size[x];
	if(!rt || f[rt] > f[x]) rt = x;
}
void dfs(int x) {
	for(int i=g[x]; i; i=next[i]) {
		if(to[i] == fa[x]) continue;
		fa[to[i]] = x; dfs(to[i]);
	}
	len = 0;
	for(int i=g[x]; i; i=next[i]) {
		if(to[i] == fa[x]) continue;
		a[++len] = Ha[to[i]];
	} a[++len] = 1;
	std::sort(a+1,a+len+1);
	Ha[x] = Trie::insert();
	if(x != rt) modify(Ha[x],1);
}
void getans(int x , int d) {
	if(sum+d >= sans) sans = sum+d , ans = x;
	for(int i=g[x]; i; i=next[i]) {
		if(to[i] == fa[x]) continue;
		modify(Ha[x],-1);
		getans(to[i],d+1);
		modify(Ha[x],1);
	}
}
int main() {
	n = F();
	for(int i=1; i<n; ++i) {
		int a = F() , b = F();
		ins(a,b);
	}
	getrt(1);
	fa[rt] = 0; dfs(rt);
	getans(rt,0);
	printf("%d\n",ans);
}

E.

#include <stdio.h>
#include <vector>
#include <iostream>
#define inf 233333333
using namespace std;
inline int F() { register int aa , bb , ch;
	while(ch = getchar() , (ch<'0'||ch>'9') && ch != '-'); ch == '-' ? aa=bb=0 : (aa=ch-'0',bb=1);
	while(ch = getchar() , ch>='0'&&ch<='9') aa = aa*10 + ch-'0'; return bb ? aa : -aa;
}
const int Maxn = 100005;
const int Maxm = 600005;
struct E { int a , b; } e[Maxm];
int n , m , k , q , id , val[Maxm] , ans[Maxn];
std::vector<int> vec[Maxn];
std::vector< pair<int,int> > que[Maxn];
int fa[Maxm] , c[Maxm][2] , mx[Maxm] , mn[Maxm] , st[Maxm] , top;
bool rev[Maxm];
bool isroot(int x) { return (c[fa[x]][0] != x && c[fa[x]][1] != x); }
void update(int x) {
	int lc = c[x][0] , rc = c[x][1];
	mx[x] = x;
	if(lc && val[mx[lc]] > val[mx[x]]) mx[x] = mx[lc];
	if(rc && val[mx[rc]] > val[mx[x]]) mx[x] = mx[rc];
}
void downpush(int x) {
	int lc = c[x][0] , rc = c[x][1];
	if(rev[x]) {
		if(lc) rev[lc] ^= 1;
		if(rc) rev[rc] ^= 1;
		c[x][0] = rc; c[x][1] = lc;
		rev[x] = 0;
	}
}
void rotate(int x) {
	int y = fa[x] , z = fa[y] , p,q;
	if(x == c[y][0]) p = 0; else p = 1; q = p^1;
	if(!isroot(y)) {
		if(y == c[z][0]) c[z][0] = x;
		else c[z][1] = x;
	}
	fa[x] = z; fa[y] = x; fa[c[x][q]] = y;
	c[y][p] = c[x][q]; c[x][q] = y;
	update(y); update(x);
}
void splay(int x) {
	st[++top] = x;
	for(int i=x; !isroot(i); i=fa[i]) st[++top] = fa[i];
	while(top) downpush(st[top--]);
	while(!isroot(x)) {
		int y = fa[x] , z = fa[y];
		if(!isroot(y)) {
			if((x == c[y][0]) ^ (y == c[z][0])) rotate(x);
			else rotate(y);
		} rotate(x);
	}
}
void access(int x) { for(int t=0; x; t=x,x=fa[x]) { splay(x); c[x][1] = t; update(x); } }
void makeroot(int x) { access(x); splay(x); rev[x] ^= 1; }
void link(int x , int y) { makeroot(x); fa[x] = y; }
void cut(int x , int y) { makeroot(x); access(y); splay(y); c[y][0] = fa[x] = 0; }
int findroot(int x) {
	access(x); splay(x);
	while(c[x][0]) x = c[x][0];
	return x;
}
int BIT[Maxn];
#define lowbit(x) ((x) & -(x))
void add(int x , int val) { for(; x <= n; x += lowbit(x)) BIT[x] += val; }
int query(int x) {
	int val = 0;
	for(; x; x-=lowbit(x)) val += BIT[x];
	return val;
}
int main() {
	n = F() , k = F() , m = F();
	for(int i=1; i<=n; ++i) { val[i] = -inf; mx[i] = i; }
	id = n;
	for(int i=1; i<=m; ++i) {
		e[i].a = F() , e[i].b = F();
		if(e[i].a > e[i].b) swap(e[i].a,e[i].b);
		val[++id] = e[i].b; mx[id] = id;
		vec[e[i].a].push_back(i);
	}
	int q = F();
	for(int i=1; i<=q; ++i) {
		int a = F() , b = F();
		que[a].push_back(make_pair(b,i));
	}
	for(int i=n; i; --i) {
		for(int j=0; j<vec[i].size(); ++j) {
			int now = vec[i][j];
			if(findroot(e[now].a) != findroot(e[now].b)) {
				link(e[now].a,n+now); link(e[now].b,n+now);
				add(val[n+now],1);
			}
			else {
				makeroot(e[now].a); access(e[now].b); splay(e[now].b);
				int x = mx[e[now].b];
				if(val[x] > val[n+now]) {
					cut(e[x-n].a,x); cut(e[x-n].b,x); add(val[x],-1);
					link(e[now].a,n+now); link(e[now].b,n+now); add(val[n+now],1);
				}
			}
		}
		for(int j=0; j<que[i].size(); ++j) {
			int qr = que[i][j].first , qi = que[i][j].second;
			ans[qi] = (qr - i + 1) - query(qr);
		}
	}
	for(int i=1; i<=q; ++i) printf("%d\n",ans[i]);
}
Category: Codeforces | Tags: | Read Count: 312

登录 *


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