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]);
}
评论 (0)
