muti多校-6

自用笔记算法

muti多校-6

HDU 6096

题目要求

给出n个单词和q次询问
每次询问包括一个前缀和后缀 问满足条件的单词共多少个

参考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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>
#define pb push_back
#define maxn 500050
using namespace std;
char s[maxn],t[maxn],st[maxn*2];
struct Trie{
	int num,root,next[maxn*2][26],v[maxn*2];
	vector<int>g[2*maxn];
	int newnode(){
		for(int i=0;i<26;i++) next[num][i]=-1;
		v[num]=0;
		return num++;
	}
	void init(){
		num=0;
		for(int i=0;i<2*maxn;i++) g[i].clear();
		root=newnode();
	}
	void build(char *s,int len){
		int lens=strlen(s);
		int now=root;
		for(int i=0;i<lens;i++){
			int id=s[i]-'a';
			if(next[now][id]==-1) next[now][id]=newnode();
			now=next[now][id];
			g[now].pb(len);
			v[now]++;
		}
	}
	void dfs(int x){
		sort(g[x].begin(),g[x].end());
		for(int i=0;i<26;i++){
			int temp=next[x][i];
			if(temp!=-1) dfs(temp);
		}
	}
}trie;
int main(){
	int T; scanf("%d",&T);
	while(T--){
		int n,q;
		scanf("%d%d",&n,&q);
		trie.init();
		for(int i=0;i<n;i++){
			scanf("%s",s);
			int len=strlen(s);
			for(int j=0;j<len;j++){
				st[2*j]=s[j];
				st[2*j+1]=s[len-j-1];
			}
			st[len*2]='\0';
			trie.build(st,len);
		}
		trie.dfs(0);
		while(q--){
			scanf("%s %s",&s,&t);
			int len1=strlen(s);
			int len2=strlen(t);
			int len=max(len1,len2);
			int sum=len1+len2;
			for(int i=0;i<len;i++){
				if(i<len1) st[2*i]=s[i];
				else st[2*i]='*';
				if(i<len2) st[2*i+1]=t[len2-i-1];
				else st[2*i+1]='*';
			}
			len*=2;
			queue<int>q[2];
			q[0].push(0);
			int ans=0,temp=0;
			for(int i=0;i<len;i++){
				int id=st[i]-'a';
				while(!q[temp].empty()){
					int now=q[temp].front(); q[temp].pop();
					if(st[i]=='*'){
						for(int j=0;j<26;j++){
							int x=trie.next[now][j];
							if(x!=-1) q[1-temp].push(x);
						}
					}
					else{
						int x=trie.next[now][id];
						if(x!=-1) q[1-temp].push(x);
					}
				}
				temp=1-temp; 
			}
			while(!q[temp].empty()){
				int now=q[temp].front();
				q[temp].pop();
				int pos=lower_bound(trie.g[now].begin(),trie.g[now].end(),sum)-trie.g[now].begin();
				ans+=trie.v[now];
				ans-=pos;
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}

思路

普通trie的情况下加了后缀的限制
存储单词的时候按照第一位 第n位 第2位 第n-1位这样存储 例如cedf存储为cfdeedfc 相当于奇数位正序 偶数位逆序
查询前后缀的时候同理 如果前后缀大小不等用*补齐 代表可以用任何字母代替 例如ce f存储为cfe*
字典树存放的为：num代表给每个结点的编号 当有新的结点时候调用newnode num++ next模拟指针 v代表经过该结点的字符串个数
g存储经过该结点的所有字符串的长度
用2个队列互相更新 从0的根开始 q[0]和q[1]互相转换 相当于向下遍历字典树的过程
通过更新队列后逐个弹出g[temp]里的结点序号 通过lower_bound找到该长度在g中的位置 用v-pos就是答案 表示所有经过该结点的
字符串个数减去长度小于sum就是答案 只有大于sum才能在前后缀的基础上继续延伸满足题意
注意：第一个st应加\0 不然strlen不能处理

HDU 6098

题目要求

给出数组n 要求从i=2开始到n 共n-1个数字 依次输出A中index%i!=0的最大值

参考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
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
template<typename T> inline void read(T &x){x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;}
inline void out(int x){if(x>9) out(x/10);putchar(x%10+'0');}
vector<pii>a;
int dp[maxn];
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t; read(t);
    while(t--){
        a.clear();
        mm(dp,0);
        int n; read(n);
        for(int i=1;i<=n;i++){
            int x; read(x);
            a.pb(mp(x,i));
        }
        sort(a.begin(),a.end(),greater<pii>());
        int len=a.size();
        for(int i=2;i<=n;i++){
            for(int j=0;j<len;j++){
                int num=a[j].fi,id=a[j].se;
                if(id%i!=0){
                    dp[i]=num;
                    break;
                }
            }
        }
        for(int i=2;i<=n;i++){
            if(i==2) printf("%d",dp[i]);
            else printf(" %d",dp[i]);
        }
        printf("\n");
    }
    return 0;
}

思路

任何nlogn算法都可以卡过
这里介绍一种：给数组A从大到小排序 从最大数开始 dp数组预处理出index%i!=0的最大数
实际情况是只要找到第一个满足该位置条件的直接保存退出判断下一个

HDU 6103

题目要求

定义2个长度为n的字符串的dist为Ai-B(n-1-i) i从0到n-1 类似于与回文 A的第0位-B的第n-1位+A的第1位+B的第n-1位···
现在给出一个string 要求在里面找出2个子串满足长度最大 且他们的dist和不能超过m

参考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
#include<bits/stdc++.h>
#define maxn 25005
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
template<typename T> inline void read(T &x){x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;}
inline void out(int x){if(x>9) out(x/10);putchar(x%10+'0');}
char s[maxn];
int main(){
//    freopen("input.txt","r",stdin);
    int t; scanf("%d",&t);
    while(t--){
        int m; scanf("%d",&m);
        scanf("%s",s+1);
        int n=strlen(s+1);
        int ans=0;
        queue<int>q;
        for(int mid=1;mid<=n;mid++){
            while(!q.empty()) q.pop();
            int now=0,len=0;
            for(int l=1;;l++){
                int i=mid-l,j=mid+l-1;
                if(i<1 || j>n) break;
                now+=abs(s[j]-s[i]);
                len++;
                if(now>m){
                    if(!q.empty()){
                        now-=q.front();
                        q.pop();
                        len--;
                    }
                }
                q.push(abs(s[j]-s[i]));
                if(len>ans && now<=m) ans=len;
            }
        }
        for(int mid=1;mid<=n;mid++){
            while(!q.empty()) q.pop();
            int now=0,len=0;
            for(int l=1;;l++){
                int i=mid-l,j=mid+l;
                if(i<1 || j>n) break;
                now+=abs(s[j]-s[i]);
                len++;
                if(now>m){
                    if(!q.empty()){
                        now-=q.front();
                        q.pop();
                        len--;
                    }
                }
                q.push(abs(s[j]-s[i]));
                if(len>ans && now<=m) ans=len;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

思路

枚举1-n的所有位置作为mid 向两边扩散
再枚举向两边扩散的距离 两种情况是因为剩余的个数有奇数和偶数个两种 所以第二种情况跳了一格满足了奇数
扩散中越界break并且实时更新now和ans 如果now大于m 那么从队列中去掉队首 即入队最早的元素(最接近mid)

HDU 6105

题目要求

给出一棵树，Alice 和 Bob 轮流操作， Alice先手， Alice的操作是选一个未染色的点将其染成白色，Bob的操作是选一个未染色的点将其染成黑色
并且和这个点有直连边的点也被强制染成黑色（无论这些直连点之前是否有颜色）Bob还有一个小技能是去掉一条边，最后当所有点都有颜色的时候，
如果有白色点则Alice赢，否则Bob赢。

参考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
#include<bits/stdc++.h>
#define maxn 550
#define pb push_back
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
vector<int>e[maxn];
int flag;
void dfs(int x){
    int num=0,len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(e[next].size()==0) num++;
        if(num>=2){
            flag=1;
            return;
        }
        dfs(next);
    }
}
int main(){
//    freopen("input.txt","r",stdin);
    int t; scanf("%d",&t);
    while(t--){
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=0;i<=n;i++) e[i].clear();
        for(int i=2;i<=n;i++){
            int x; scanf("%d",&x);
            e[x].pb(i);
        }
        flag=0;
        dfs(1);
        if(n&1 || n/2-1>k || flag) puts("Alice");
        else puts("Bob");
    }
    return 0;
}

思路

我们通过总结发现只要满足下面四个任意一个条件Alice就必胜，否则Bob获胜
1.Bob的技能使用次数不足以把所有节点分成若干两个一组的点对。
2.节点个数为奇数。
3.存在大于等于两个节点的父亲节点是同一个。
4.某个节点存在大于等于两个子节点，其下面节点的个数(包括自身)为奇数。

1.只有在两个一组的情况下，Alice把一个点染成白色，Bob把另一个点染成黑色，同时前一个点也变成了黑色，以此类推，Bob能获胜，
否则Bob无法每次都把Alice染的白色变为黑色。
2.奇数的话，其余都成了两个一组，并能全部为黑色，但剩下的一个点会被Alice染成白色，而Bob无法操作了。
3.这种情况下，Alice只要把父亲节点染为白色，然后Bob只能染其中一个叶子节点，虽然父亲节点也变成了黑色，但只要Alice把另一个叶子节点染成白色，
Bob对这个点就无可奈何了(注意前提是叶子节点)。
4.这样的话，由于子节点下的节点个数为奇数，这样的点只有一个时，我可以加上它的父节点使这些点的个数为偶数(暂不考虑子树中还有不满足的情况)，
但大于等于两个的话，必然留下至少一棵子树节点个数为奇数(条件2)，即Alice必胜。

HDU 6106

题目要求

班级上的人参加活动
给出参加A B C 参加A和B A和C B和C AB和C的人数 要求判断至少参加一个活动的人数
有的数据自相矛盾需要忽略

参考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
#include<bits/stdc++.h>
#define maxn 100000
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
template<typename T> inline void read(T &x){x=0;T f=1;char ch;do{ch=getchar();if(ch=='-')f=-1;}while(ch<'0'||ch>'9');do x=x*10+ch-'0',ch=getchar();while(ch<='9'&&ch>='0');x*=f;}
inline void out(int x){if(x>9) out(x/10);putchar(x%10+'0');}
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("ouput.txt","w",sdout);
    int t; read(t);
    while(t--){
        int n; read(n);
        int ans=-1;
        for(int i=1;i<=n;i++){
            int a,b,c,ab,bc,ac,abc;
            read(a),read(b),read(c),read(ab),read(bc),read(ac),read(abc);
            int x1=a-ab-ac+abc;
            int x2=b-ab-bc+abc;
            int x3=c-ac-bc+abc;
            int x4=ab-abc;
            int x5=ac-abc;
            int x6=bc-abc;
            int x7=abc;
            int re;
            if(x1<0 || x2<0 || x3<0 || x4<0 || x5<0 || x6<0 || x7<0) re=0;
            else re=x1+x2+x3+x4+x5+x6+x7;
            ans=max(ans,re);
        }
        out(ans); printf("\n");
    }
    return 0;
}

思路

画出图 相当于容斥原理 要求图上的每个部分人数都必须大于0 小于0忽略
最后相加求最大值就是答案

本文标题:muti多校-6

文章作者:Hippopmonkey

发布时间:2017-08-11, 14:59:32

最后更新:2017-08-21, 23:57:56

原始链接:http://xuboming8.github.io/2017/08/11/muti多校-6/

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

文章目录
  1. 1. muti多校-6
    1. 1.1. HDU 6096
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. HDU 6098
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 6103
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. HDU 6105
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. HDU 6106
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
|