Jan.5th
注:黑粗体为超链接
啊~遥想上次写博客已是半年前了啊又要跳进这个大坑了
直接把≥5的都反一下,除了在第一位的9。
一开始不理解题意WA了3发真是可以吔屎了
按照斜率排序之后直接去重
发现自己太傻不会设eps 不会设inf 也可以吔屎了
先把每个单词构建字典树之后DFS
DFS时标记是否已有一位不同
实力学会字典树(现在才会真是对不起啊)
(其实是因为hash使不过去才去学trie的)
C++ Code By WTRC
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"); } } |
二分摧毁最长机器人队列长度
用单调队列维护每个$[i,i+mid-1]$的最大值
判断是否≤k
注意二分下界为0
其实我觉得比C水多了
C++ Code By WTRC
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]]); } |
——————————————————————————————
Jan 12, 2016 01:57:29 PM
人群之中为什么费老板是绿的呢
Jan 12, 2016 02:02:05 PM
人群之中为什么费老板是绿的呢
Jan 12, 2016 08:01:20 PM
@qiancl:
@hzq84621:
有什么办法0.0