2017广西邀请赛

自用笔记算法

2017 广西邀请赛

HDU 6182

题目要求

问有多少k满足 k的k次方小于等于n n小于等于1e18

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
#define LL long long 
using namespace std;
LL qpow(LL x,LL y){LL re=1,base=x;while(y){if(y&1)re*=base;base*=base;y>>=1;}return re;}
int main(){
//    freopen("input.txt","r",stdin);
    LL n;
    while(cin>>n){
        LL l=1,r=15;
        LL ans=1;
        while(l<=r){
            LL mid=(l+r)>>1;
            if(qpow(mid,mid)<=n){
                ans=mid;
                l=mid+1;
            }
            else r=mid-1;
        }
        cout<<ans<<endl;
    }
    return 0;
}

思路

只有最多15种情况 暴力就行

HDU 6183

题目要求

一个空的坐标系，有4种操作：
1 x y c表示在(x, y)点染上颜色c；
2 X y1 y2表示查询在(1, y1)到(X, y2)范围内有多少种不同的颜色：
0表示清屏；
3表示程序退出（0<=x, y<=1000000, 0<=c<=50）

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 4000050
#define inf 0x3f3f3f3f
#define mm(a,b) memset(a,b,sizeof(a))
#define lson tree[rt].l,l,mid
#define rson tree[rt].r,mid+1,r
using namespace std;
struct T{
	int Min;
	int l,r;
}tree[maxn];
int root[55],cnt,op,flag;
void init(){
	mm(tree,0),mm(root,0);
	cnt=0;
}
void update(int &rt,int l,int r,int x,int y){
	if(!rt){
		rt=++cnt;
		tree[rt].Min=x;
	}
	tree[rt].Min=min(tree[rt].Min,x);
	if(l==r) return;
	int mid=(l+r)>>1;
	if(mid>=y) update(lson,x,y);
	else update(rson,x,y);
	
}
void query(int rt,int l,int r,int L,int R,int x){
	if(flag || !rt) return;
	if(l>=L && r<=R){
		if(tree[rt].Min<=x) flag=1;
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=L) query(lson,L,R,x);
	if(mid<R) query(rson,L,R,x);
}
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d",&op)!=EOF){
		if(op==3) break;
		else if(op==0) init();
		else if(op==1){
			int x,y,c;
			scanf("%d%d%d",&x,&y,&c);
			update(root[c],1,1000000,x,y);
		}
		else{
			int x,y1,y2;
			scanf("%d%d%d",&x,&y1,&y2);
			int ans=0;
			for(int i=0;i<=50;i++){
				flag=0;
				query(root[i],1,1000000,y1,y2,x);
				ans+=flag;
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}

思路

颜色只有50种，可以建50棵线段树然后暴力
对于每一种颜色，因为查询的横坐标是1到X，所以对于每个y，你只需要知道离y轴最近的那个点在哪里
这样的话就可以按y坐标建树，查询的时候判断下范围内有没有点即可
注意防止炸内存 可以用每个现有的结点的编号是++cnt的动态开点方式 并rt带&可以有效的返回改颜色root的编号
最后暴力50种颜色 判断维护的x最小值在不在要求的之内 若没有这种颜色直接跳过

HDU 6184

题目要求

n个点m条边的无向图，问有多少个A-structure
其中A-structure满足V=(A,B,C,D) && E=(AB,BC,CD,DA,AC)

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define LL long long
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
set<LL>s;
int n,m,limit;
vector<int>e[maxn];
int out[maxn],vis[maxn],linker[maxn];
void init(){
	s.clear();
	for(int i=1;i<=n;i++) e[i].clear();
	mm(out,0),mm(vis,0),mm(linker,0);
	limit=sqrt(m+0.5);
}
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d",&n,&m)!=EOF){
		init();
		for(int i=1;i<=m;i++){
			int u,v;
			scanf("%d%d",&u,&v);
			e[u].push_back(v);
			e[v].push_back(u);
			out[v]++,out[u]++;
			s.insert((LL)u*n+v);
			s.insert((LL)v*n+u);
		}
		LL ans=0;
		for(int i=1;i<=n;i++){
			vis[i]=1;
			int len=e[i].size();
			for(int j=0;j<len;j++){
				int next=e[i][j];
				linker[next]=i;
			}
			for(int j=0;j<len;j++){
				int next=e[i][j];
				int sum=0;
				if(vis[next]) continue;
				if(out[next]<=limit){
					int len2=e[next].size();
					for(int k=0;k<len2;k++){
						int next2=e[next][k];
						if(linker[next2]==i) sum++; 
					}
				}
				else{
					for(int k=0;k<len;k++){
						int next2=e[i][k];
						if(s.find((LL)next2*n+next)!=s.end()) sum++;
					}
				}
				ans+=(LL)sum*(sum-1)/2;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

思路

可以看出A-structure是由两个有公共边的三元环构成的
msqrt(m)暴力三元环就好了
1.统计每个点的度数
2.入度<=sqrt(m)的分为第一类，入度>sqrt(m)的分为第二类
3.对于第一类，连续暴力依次连接的三个点 判断第三个点和第一个点是否相连
因为m条边最多每条边遍历一次，然后暴力的点的入度<=sqrt(m)，所以复杂度约为O(msqrt(m))
4.对于第二类，直接暴力任意第一个点和连接第一个点的另两个点，判断这三个点是否构成环，因为这一类点的个数不会超过sqrt(m)个，
所以复杂度约为O(sqrt(m)^3)=O(msqrt(m))
5.判断两个点是否连接可以用set，map和Hash都行
考虑每一个边时，如果有K个点跟这个边的两个端点都相连，那么有CK2种方案

HDU 6185

题目要求

4×n的方格用1×2和2×1的矩形去填 有多少种方法
n的范围为1e18

参考AC代码

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
#include<bits/stdc++.h>
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 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;}
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));
    }
}

思路

用普通的求k×n的矩阵快速幂方法打表
接着带入杜教的找线性规律的模版就好了

HDU 6186

题目要求

有n个数字 求删除某个数字后剩余的总体与 或 异或值
多次询问

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,q;
int a[maxn];
int pre1[maxn],pre2[maxn],pre3[maxn];
int suf1[maxn],suf2[maxn],suf3[maxn];
void init(){
    mm(pre1,0),mm(pre2,0),mm(pre3,0);
    mm(suf1,0),mm(suf2,0),mm(suf3,0);
}
int main(){
//    freopen("input.txt","r",stdin);
    while(scanf("%d%d",&n,&q)!=EOF){
        init();
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        pre1[1]=a[1],pre2[1]=a[1],pre3[1]=a[1];
        suf1[n]=a[n],suf2[n]=a[n],suf3[n]=a[n];
        for(int i=2;i<=n;i++){
            pre1[i]=pre1[i-1]&a[i];
            pre2[i]=pre2[i-1]|a[i];
            pre3[i]=pre3[i-1]^a[i];
        }
        for(int i=n-1;i>=1;i--){
            suf1[i]=suf1[i+1]&a[i];
            suf2[i]=suf2[i+1]|a[i];
            suf3[i]=suf3[i+1]^a[i];
        }
        while(q--){
            int x;
            scanf("%d",&x);
            if(x==1){
                printf("%d %d %d\n",suf1[2],suf2[2],suf3[2]);    
            }
            else if(x==n){
                printf("%d %d %d\n",pre1[n-1],pre2[n-1],pre3[n-1]);
            }
            else{
                printf("%d %d %d\n",pre1[x-1]&suf1[x+1],pre2[x-1]|suf2[x+1],pre3[x-1]^suf3[x+1]);
            }
        }
    }
    return 0;
}

思路

on求前后缀
o1询问

HDU 6187

题目要求

总权值-最大生成树权值和

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 200050
#define inf 0x3f3f3f3f
#define pb push_back
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
struct edge{
	int u,v,w;
	edge(int u,int v,int w):u(u),v(v),w(w){}
	bool operator < (const edge& x) const{
		return w>x.w;
	}
};
int n,m,tol;
int cnt;
int p[maxn];
vector<edge>e;
void init(){
	e.clear();
	tol=0,cnt=0;
}
int find(int x){
	return x==p[x]?x:p[x]=find(p[x]);
}
int kruskal(){
	int ans=0;
	sort(e.begin(),e.end());
	for(int i=0;i<=n;i++) p[i]=i;
	for(int i=0;i<m;i++){
		int x=find(e[i].u),y=find(e[i].v);
		if(x!=y){
			ans+=e[i].w;
			p[x]=y;
			cnt++;
		}
	}
	return ans;
}
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d%d",&n,&m)!=EOF){
		init();
		for(int i=1;i<=n;i++){
			int x,y;
			scanf("%d%d",&x,&y);
		}
		for(int i=1;i<=m;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			tol+=w;
			e.pb(edge(u,v,w));
		}
		int ans=kruskal();
		printf("%d %d\n",m-cnt,tol-ans);
	}
	return 0;
}

思路

注意删除的边数是m-cnt而不是m-n+1

HDU 6188

题目要求

输入一个n，接下来有n个数，让你求出能组成最多的对子或者顺子的和。
对子: (2,2)，顺子: (1,2,3)。

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 1000050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int hashh[maxn];
int n;
int main(){
//	freopen("input.txt","r",stdin);
	while(scanf("%d",&n)!=EOF){
		mm(hashh,0);
		for(int i=1;i<=n;i++){
			int x;
			scanf("%d",&x);
			hashh[x]++;
		}
		int ans=0;
		for(int i=1;i<=1000000;i++){
			if(hashh[i] && hashh[i-1] && hashh[i-2] && i>=3){
				hashh[i]--,hashh[i-1]--,hashh[i-2]--;
				ans++;
			}
			ans+=hashh[i]/2;
			hashh[i]%=2;
		}
		printf("%d\n",ans);
	}
	return 0;
}

思路

贪心
当前数能作为某个顺子的最大值，则取顺子；
否则能取对子，则取对子。

HDU 6191

题目要求

给你一棵有根树，树上每个节点有一个值，每次询问以u为根节点的子树异或上x的最大值

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 200050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int bin[30];
int n,m,cnt;
int a[maxn],b[maxn],root[maxn];
vector<int>e[maxn];
int in[maxn],out[maxn];
void init(){
	for(int i=0;i<=n;i++) e[i].clear();
	mm(in,0),mm(out,0),mm(root,0);
	cnt=0;
}
struct trie{
    int cnt;
    int ch[maxn*30][2],sum[maxn*30];
    void init(){
        cnt = 0;
        mm(ch,0);
    	mm(sum,0);
    }
    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;
void dfs(int x,int fa){
	in[x]=++cnt;
	root[cnt]=trie.insert(root[cnt-1],a[x]);
	int len=e[x].size();
	for(int i=0;i<len;i++){
		int next=e[x][i];
		if(next==fa) continue;
		dfs(next,x);
	}
	out[x]=cnt;
}
int main(){
//	freopen("input.txt","r",stdin);
	bin[0]=1;
	for(int i=1;i<=30;i++) bin[i]=bin[i-1]<<1;
	while(scanf("%d%d",&n,&m)!=EOF){
		init();
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=2;i<=n;i++){
			int x;
			scanf("%d",&x);
			e[x].push_back(i);
		}
		trie.init();
		dfs(1,0);
		while(m--){
			int x,y;
			scanf("%d%d",&x,&y);
			printf("%d\n",trie.query(root[in[x]-1],root[out[x]],y));
		}
	}
	return 0;
}

思路

按照dfs序建关于数字的二进制可持久化字典树就好了

本文标题:2017广西邀请赛

文章作者:Hippopmonkey

发布时间:2017-09-01, 15:44:29

最后更新:2017-09-02, 23:21:27

原始链接:http://xuboming8.github.io/2017/09/01/2017广西邀请赛/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 2017 广西邀请赛
    1. 1.1. HDU 6182
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. HDU 6183
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 6184
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. HDU 6185
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. HDU 6186
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. HDU 6187
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
    7. 1.7. HDU 6188
      1. 1.7.1. 题目要求
      2. 1.7.2. 参考AC代码
      3. 1.7.3. 思路
    8. 1.8. HDU 6191
      1. 1.8.1. 题目要求
      2. 1.8.2. 参考AC代码
      3. 1.8.3. 思路
|