1
5
2016
3

Diary of OI

Jan.5th

注:黑粗体为超链接

啊~遥想上次写博客已是半年前了啊又要跳进这个大坑了
直接把≥5的都反一下,除了在第一位的9。
一开始不理解题意WA了3发真是可以吔屎了
按照斜率排序之后直接去重
发现自己太傻不会设eps   不会设inf   也可以吔屎了
 
先把每个单词构建字典树之后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]==NULLcontinue;
        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");
    }
}
 
二分摧毁最长机器人队列长度
用单调队列维护每个$[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: 398
Avatar_small
hzq84621 说:
Jan 12, 2016 01:57:29 PM

人群之中为什么费老板是绿的呢

Avatar_small
qiancl 说:
Jan 12, 2016 02:02:05 PM

人群之中为什么费老板是绿的呢

Avatar_small
WasteRice 说:
Jan 12, 2016 08:01:20 PM

@qiancl:
@hzq84621:
有什么办法0.0


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com