Diary of OI

1
5
2016

Jan.5th

注：黑粗体为超链接

啊~遥想上次写博客已是半年前了啊

又要跳进这个大坑了

Codeforces514A

直接把≥5的都反一下，除了在第一位的9。

一开始不理解题意WA了3发真是可以吔屎了

Codeforces514B

按照斜率排序之后直接去重

发现自己太傻不会设eps 不会设inf 也可以吔屎了

Codeforces514C

先把每个单词构建字典树之后DFS

DFS时标记是否已有一位不同

实力学会字典树~~（现在才会真是对不起啊）~~

（其实是因为hash使不过去才去学trie的

）

C++ Code By WTRC

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

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Per(x,a,b) for (int x=a;x>=b;x--)
#define ll long long
using namespace std;
inline int IN(){
    int x=0,ch=getchar(),f=1;
    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
    if (ch=='-'){f=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int len,n,m;
struct Trie{
    Trie *next[3];
    bool fin;
    Trie(){Rep(i,0,2) next[i]=NULL;fin=0;}
}*root;
char s[600005];
void Build(Trie *now){
    len=strlen(s);
    Rep(i,0,len-1){
        int to=s[i]-'a';
        if (now->next[to]==NULL) now->next[to]=new Trie;
        now=now->next[to];
    }
    now->fin=1;
}
bool DFS(Trie *now,int nl,bool chg){
    if (nl==len) return chg&(now->fin);
    Rep(i,0,2){
        if (now->next[i]==NULL) continue;
        if (i!=s[nl]-'a'){
            if (chg) continue;
            if (DFS(now->next[i],nl+1,1)) return 1;
        }
        else if (DFS(now->next[i],nl+1,chg)) return 1;
    }
    return 0;
}
int main(){
    root=new Trie;
    n=IN(),m=IN();
    Rep(i,1,n){gets(s);Build(root);}
    Rep(i,1,m){
        gets(s);len=strlen(s);
        if (DFS(root,0,0)) puts("YES");else puts("NO");
    }
}

Codeforces 514D

二分摧毁最长机器人队列长度

用单调队列维护每个$[i,i+mid-1]$的最大值

判断是否≤k

注意二分下界为0

其实我觉得比C水多了

C++ Code By WTRC

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

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<ctime>
#include<cstdlib>
#include<string>
#include<queue>
#define Rep(x,a,b) for (int x=a;x<=b;x++)
#define Per(x,a,b) for (int x=a;x>=b;x--)
#define ll long long
using namespace std;
inline int IN(){
    int x=0,ch=getchar(),f=1;
    while (!isdigit(ch)&&(ch!='-')&&(ch!=EOF)) ch=getchar();
    if (ch=='-'){f=-1;ch=getchar();}
    while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,k,h[5],t[5],Q[5][100005];
int a[100005][5];
bool solve(int len){
    Rep(i,0,m-1) h[i]=1,t[i]=0;
    int tail=len,Sum=0;
    Rep(i,1,len) Rep(j,0,m-1){
        while (t[j]>=h[j]&&Q[j][t[j]]<a[i][j]) t[j]--;
        Q[j][++t[j]]=a[i][j];
    }
    Rep(i,0,m-1) Sum+=Q[i][h[i]];
    if (Sum<=k) return 1;
    Rep(i,len+1,n){
        Sum=0;
        Rep(j,0,m-1){
            if (Q[j][h[j]]==a[i-len][j]) h[j]++;
            while (t[j]>=h[j]&&Q[j][t[j]]<a[i][j]) t[j]--;
            Q[j][++t[j]]=a[i][j];
            Sum+=Q[j][h[j]];
        }
        if (Sum<=k) return 1;
    }
    return 0;
}
int main(){
    n=IN(),m=IN(),k=IN();
    Rep(i,1,n) Rep(j,0,m-1) a[i][j]=IN();
    int l=0,r=n;
    while (l<r){
        int mid=l+r+1>>1;
        if (solve(mid)) l=mid;
            else r=mid-1;
    }
    solve(l);
    Rep(i,0,m-1) printf("%d ",Q[i][h[i]]);
}

——————————————————————————————

Category: Diary | Tags: codeforces | Read Count: 823