2017ACM-ICPC广西邀请赛-重现赛

Posted by Cww97 on 2017-08-31

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/77753648
这是在厚林工作室4个人打的一场

骚呢

两年没回去了

这里写图片描述
这里写图片描述

拿lzy的号打,打的被老刘查水表了

这里写图片描述
这里写图片描述

01

枚举kkk^kkk,k≤15k 15k≤15。
看到我的TTT就知道我是怎么wa的了。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll powder(ll a,ll n){
if(n==0) return 1ll;
ll ret = powder(a,n/2);
ret = ret * ret;
if(n&1) return ret*a;
return ret;
}

int main(){
int T;
ll n;
while(cin>>n){
int cnt = 0;
for(ll i=1;i<=15;i++){
if(powder(i,i)<=n)
cnt++;
}
cout<<cnt<<endl;
}
return 0;
}

#02 Color it

线段树,按y排,存x坐标,维护min

按x排存y坐标也行的,

防止炸空间,可以离散化或者像我这样,用到哪建到哪,最多是nlogn的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6 + 7;

bool getCol;

struct segTree{
#define val(x) tree[x].val
#define lson tree[rt].lc, l, m
#define rson tree[rt].rc, m+1, r
static const int TREE_N = N * 3 + 3e5;
struct node{
int lc, rc, val;
} tree[TREE_N];
int tot, root[55];

void build(){
memset(tree, 0, sizeof(tree));
memset(root, 0, sizeof(root));
tot = 0;
}

//p: pos, v: val
void add(int p, int v, int &rt, int l, int r){
if (!rt) val(rt = ++tot) = v;
val(rt) = min(val(rt), v);
if (l == r) return;
int m = (l + r) >> 1;
if (p <= m) add(p, v, lson);
else add(p, v, rson);
}

void query(int L, int R, int v, int rt, int l, int r){
if(getCol || !rt) return;
if(L <= l && r <= R){
if(val(rt) <= v) getCol = 1; return;
}
int m = (l + r) >> 1;
if (L <= m) query(L, R, v, lson);
if (R > m) query(L, R, v, rson);
}
#undef val(x)
#undef lson
#undef rson
} T;

int main(){
//freopen("in.txt", "r", stdin);
int op, x, y, c, L, R, X;
T.build();
for (; scanf("%d", &op) && op != 3;){
if (op == 0) T.build();
else if(op == 1){
scanf("%d%d%d", &x, &y, &c);
T.add(y, x, T.root[c], 1, N);
}else if(op == 2){
scanf("%d%d%d", &X, &L, &R);
int ans = 0;
for(int i = 0; i <= 50; i++){
getCol = 0;
T.query(L, R, X, T.root[i], 1, N);
if (getCol) ans++;
}
printf("%d\n",ans);
}
}
return 0;
}

03

统计有多少V=(A,B,C,D)V=(A,B,C,D)V=(A,B,C,D),E=(AB,BC,CD,DA,AC)E=(AB,BC,CD,DA,AC)E=(AB,BC,CD,DA,AC)。
考虑一个边作为对角线时,如果有K个点跟这个边的两个端点都相连,那么有CK2_{K}^{2}CK2​中方案。
统计时,让条边记录在度数比较少的点处,减少枚举次数,每次将3个边一起算贡献。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>

#define mp make_pair

using namespace std;
typedef long long ll;

const int maxn = 100005;

vector<pair<int,int> > e[maxn];

int du[maxn],u,v,n,m;
ll cnt[maxn<<2];
struct node{
int u,v;
}info[maxn<<2];

struct Node{
int idi,idep;
Node(){}
Node(int _idi,int _idep){
idi=_idi;
idep=_idep;
}
}a[maxn<<2];

int main(){
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;i++)
e[i].clear();
memset(a,0,sizeof a);
memset(du,0,sizeof du);
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
du[u]++;du[v]++;
info[i].u=u;
info[i].v=v;
}
for(int i=1;i<=m;i++){
u=info[i].u;v=info[i].v;
if(du[u] < du[v] || (du[u] == du[v] && u < v))
e[u].push_back(mp(v,i));
else e[v].push_back(mp(u,i));
}
memset(cnt,0,sizeof cnt);
for(int i=1;i<=m;i++){
u=info[i].u;v=info[i].v;
for(auto ep:e[u]) a[ep.first]=Node(i,ep.second);
for(auto ep:e[v]){
if(a[ep.first].idi==i){
cnt[i]++;
cnt[ep.second]++;
cnt[a[ep.first].idep]++;
}
}
}
ll res = 0;
for(int i=1;i<=m;i++)
res += (cnt[i]-1ll)*cnt[i]/2ll;
printf("%lld\n",res);
}
return 0;
}

04

1
Number of domino tilings of 4 X (n-1) board.

an=an−1+5an−2+an−3−an−4a_n = a_{n-1} + 5a{n-2} + a_{n-3} - a_{n-4}an​=an−1​+5an−2+an−3​−an−4​,直接用杜教板子。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

int _;
ll n;
namespace linear_seq {
const int N=10010;
ll res[N],base[N],_c[N],_md[N];

vector<ll> Md;
void mul(ll *a,ll *b,ll k) {
rep(i,0,k+k) _c[i]=0;
rep(i,0,k) if (a[i]) rep(j,0,k) _c[i+j]=(_c[i+j]+a[i]*b[j])%mod;
for (int i=k+k-1;i>=k;i--) if (_c[i])
rep(j,0,SZ(Md)) _c[i-k+Md[j]]=(_c[i-k+Md[j]]-_c[i]*_md[Md[j]])%mod;
rep(i,0,k) a[i]=_c[i];
}
int solve(ll n,VI a,VI b) {
ll ans=0,pnt=0;
ll k=SZ(a);
assert(SZ(a)==SZ(b));
rep(i,0,k) _md[k-1-i]=-a[i];_md[k]=1;
Md.clear();
rep(i,0,k) if (_md[i]!=0) Md.push_back(i);
rep(i,0,k) res[i]=base[i]=0;
res[0]=1;
while ((1ll<<pnt)<=n) pnt++;
for (int p=pnt;p>=0;p--) {
mul(res,res,k);
if ((n>>p)&1) {
for (int i=k-1;i>=0;i--) res[i+1]=res[i];res[0]=0;
rep(j,0,SZ(Md)) res[Md[j]]=(res[Md[j]]-res[k]*_md[Md[j]])%mod;
}
}
rep(i,0,k) ans=(ans+res[i]*b[i])%mod;
if (ans<0) ans+=mod;
return ans;
}
VI BM(VI s) {
VI C(1,1),B(1,1);
int L=0,m=1,b=1;
rep(n,0,SZ(s)) {
ll d=0;
rep(i,0,L+1) d=(d+(ll)C[i]*s[n-i])%mod;
if (d==0) ++m;
else if (2*L<=n) {
VI T=C;
ll c=mod-d*powmod(b,mod-2)%mod;
while (SZ(C)<SZ(B)+m) C.pb(0);
rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
L=n+1-L; B=T; b=d; m=1;
} else {
ll c=mod-d*powmod(b,mod-2)%mod;
while (SZ(C)<SZ(B)+m) C.pb(0);
rep(i,0,SZ(B)) C[i+m]=(C[i+m]+c*B[i])%mod;
++m;
}
}
return C;
}
int gao(VI a,ll n) {
VI c=BM(a);
c.erase(c.begin());
rep(i,0,SZ(c)) c[i]=(mod-c[i])%mod;
return solve(n,c,VI(a.begin(),a.begin()+SZ(c)));
}
};

int main() {
while(~scanf("%lld",&n)){
printf("%d\n",linear_seq::gao(VI{1,1, 5, 11, 36, 95, 281, 781, 2245, 6336, 18061, 51205, 145601, 413351, 1174500, 3335651, 9475901, 26915305, 76455961, 217172736},n));
}
}

05

求三种sum丢掉第k位

预处理出所有的前缀和后缀

黑康说:按位枚举???

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 1e5 + 7;
int arr[N];
int prXor[N], prAnd[N], preOr[N];
int suXor[N], suAnd[N], sufOr[N];

int main(){
//freopen("in.txt", "r", stdin);
int n, q;
for (; ~scanf("%d%d", &n, &q);){
prXor[0] = suXor[n+1] = 0;
prAnd[0] = suAnd[n+1] = ~0;
preOr[0] = sufOr[n+1] = 0;

//printf("%d\n", prAnd[0]);

for (int i = 1; i <= n; i++){
scanf("%d", &arr[i]);
prXor[i] = prXor[i-1] ^ arr[i];
prAnd[i] = prAnd[i-1] & arr[i];
preOr[i] = preOr[i-1] | arr[i];
}
for (int i = n; i >= 1; i--){
suXor[i] = suXor[i+1] ^ arr[i];
suAnd[i] = suAnd[i+1] & arr[i];
sufOr[i] = sufOr[i+1] | arr[i];
}
for (int k; q--;){
scanf("%d", &k);
int ansXor = prXor[k-1] ^ suXor[k+1];
int ansAnd = prAnd[k-1] & suAnd[k+1];
int ansOrr = preOr[k-1] | sufOr[k+1];
printf("%d %d %d\n", ansAnd, ansOrr, ansXor);
}
}
return 0;
}

06

好像是个傻逼题,然后犯了傻逼错误

贡献了-6的罚时,

国王的坐标给的那么恶心的数字,就是告诉你,国王不会在wall上,然后要让国王能到达任意地方,就要让这些wall无法形成环就可以了,所以,不是环,树嘛,要求删去的最少,求个最大生成树,然后ans=sumall−sumtreeans = sum_{all} - sum_{tree}ans=sumall​−sumtree​,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> P;
const int N = 1e5 + 7;

struct Edge{
int from,to,w;
Edge(){}
Edge(int x,int y,int z):from(x),to(y),w(z){}
bool operator < (const Edge& a) const{return w > a.w;}
} edges[N * 2];

int f[N];
int F(int x){return f[x]==x ? x : (f[x]=F(f[x]));}

bool vis[N];
P kruskal(int n, int m){
int treenum = n; //forests
for (int i = 1;i <= n; i++) f[i] = i;
sort(edges, edges + m);
int cnt = 0, ans = 0;
for (int i = 0; i < m; i++){
Edge &e = edges[i];
if (F(e.from) == F(e.to)) continue;
f[F(e.from)] = F(e.to);
treenum--;
ans += e.w;
}
return P(treenum, ans);
}

int main(){
//freopen("in.txt", "r", stdin);
int n, x, y, u, v, c, m;
for (; scanf("%d%d", &n, &m)==2;){
for (int i = 1; i <= n; i++) scanf("%d%d", &x, &y);
int all = 0;
for (int i = 0; i < m; i++){
scanf("%d%d%d", &u, &v, &c);
edges[i] = Edge(u, v, c);
all += c;
}
P p = kruskal(n, m);
printf("%d %d\n", m-(n-p.fi), all - p.se);
}
return 0;
}

07毛对子和毛顺子

贪心:取i,i-1,i-2这个顺子的时候先把i-1,i-2的对子取掉,取完再取i的对子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>

using namespace std;

int a[1000005],x,n;

int main(){
while(~scanf("%d",&n)){
memset(a,0,sizeof a);
for(int i=1;i<=n;i++){
scanf("%d",&x);
a[x]++;
}
int cnt = 0;
for(int i=1;i<=1000000;i++){
if(i>=3)
if(a[i] && a[i-1] && a[i-2]){
a[i]--;a[i-1]--;a[i-2]--;
cnt++;
}
cnt += a[i]/2;
a[i] %= 2;
}
printf("%d\n",cnt);
}
return 0;
}

08

开始打表的时候发现如果a是奇数的时候肯定是1

然后a是偶数的时候,2的因子个数很多,枚举一下就行了,后面的就为0了。

开始打表发现,a≥na na≥n的时候,几乎是所有的偶数,无脑了几发。发现a<na < na<n的时候答案不对。事实上,枚举一下较小的部分。加上后面0的部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n,a;

ll power(ll a,ll b,ll mod){
if(b==0) return 1ll;
ll ret = power(a,b/2,mod);
ret = ret * ret % mod;
if(b&1)
return ret*a%mod;
return ret;
}

ll up(ll n,ll a){
return (n + a - 1) / a;
}

int main(){
//freopen("output.txt","w",stdout);
while(~scanf("%lld%lld",&n,&a)){
if(a&1){
puts("1");
continue;
}
ll mod = 1ll<<n;
ll res = 0;
for(int i=2;i<=n;i+=2)
if(power(a,i,mod) == power(i,a,mod)) res++;
res += (1<<n) >> (up(n,a));
res -= n >> (up(n,a));
printf("%d\n",res);
}
return 0;
}

#10

【bzoj3261】最大异或和
首先,如果是区间异或的话,可以用可持续化Trie树。对于树上的可以用dfs序做。查询就查询in[u]到out[u]的的区间就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define ll long long
#define N 200005
#define inf 2000000000
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int bin[30];
int n,m;
int a[N],b[N],root[N];
struct trie{
int cnt;
int ch[N*30][2],sum[N*30];
void init(){
cnt = 0;
memset(ch,0,sizeof ch);
memset(sum,0,sizeof sum);
}
int insert(int x,int val){
int tmp,y;tmp=y=++cnt;
for(int i=29;i>=0;i--)
{
ch[y][0]=ch[x][0];ch[y][1]=ch[x][1];
sum[y]=sum[x]+1;
int t=val&bin[i];t>>=i;
x=ch[x][t];
ch[y][t]=++cnt;
y=ch[y][t];
}
sum[y]=sum[x]+1;
return tmp;
}
int query(int l,int r,int val){
int tmp=0;
for(int i=29;i>=0;i--)
{
int t=val&bin[i];t>>=i;
if(sum[ch[r][t^1]]-sum[ch[l][t^1]])
tmp+=bin[i],r=ch[r][t^1],l=ch[l][t^1];
else r=ch[r][t],l=ch[l][t];
}
return tmp;
}
}trie;

int in[N],out[N],cnt;

vector<int> e[N];

void dfs(int id,int fa){
in[id] = ++cnt;
root[cnt] = trie.insert(root[cnt-1],a[id]);
for(auto ep:e[id]){
if(ep == fa) continue;
dfs(ep,id);
}
out[id]=cnt;
}

int main(){
bin[0]=1;for(int i=1;i<=30;i++)bin[i]=bin[i-1]<<1;
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;i++) e[i].clear();
for(int i=1;i<=n;i++)a[i]=read();
for(int i=2;i<=n;i++){
int v;
scanf("%d",&v);
e[v].push_back(i);
}
cnt=0;
trie.init();
dfs(1,0);
int u,x;
//for(int i=1;i<=n;i++){
// printf("in[%d],out[%d] %d\n",in[i],out[i],i);
//}
//cout<<root[4]<<endl;
while(m--){
scanf("%d%d",&u,&x);
printf("%d\n",trie.query(root[in[u]-1],root[out[u]],x));
}
}
return 0;
}

哇哦

这里写图片描述
这里写图片描述
这里写图片描述
这里写图片描述