题目链接：
A. Kefa and First Steps
题意描述：
给出一个序列，求最长不降连续子序列多长？
解题思路：
水题，签到
代码：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 int main () 8 { 9 int e, s, num, n, Max;10 while (scanf ("%d", &n) != EOF)11 {12 scanf ("%d", &s);13 n --, num = Max = 1;14 while (n --)15 {16 scanf ("%d", &e);17 if (s <= e)18 num ++;19 else20 {21 Max = max (Max, num);22 num = 1;23 }24 swap (s, e);25 }26 printf ("%d\n", max (Max, num));27 }28 return 0;29 }
题目链接：
B. Kefa and Company
题目描述：
一群人去参加庆祝趴，每个人都有两个属性(贡献，身价)，在庆祝趴里面身价最大的和身价最小的差值不能大于等于d，问庆祝趴内所有人的总贡献最大为多少？
解题思路：
排序 + 取尺，先按照身价升序sort一下，然后设置两个指针取尺就好。
代码：
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 typedef __int64 LL; 8 const int maxn = 100010; 9 struct node10 {11 LL x, y;12 }stu[maxn];13 bool cmp (node a, node b)14 {15 return a.x < b.x;16 }17 int main ()18 {19 LL n, d;20 while (scanf ("%I64d %I64d", &n, &d) != EOF)21 {22 stu[0].x = stu[0].y = 0;23 for (int i=1; i<=n; i++)24 scanf ("%I64d %I64d", &stu[i].x, &stu[i].y);25 sort (stu+1, stu+n+1, cmp);26 for (int i=1; i<=n; i++)27 stu[i].y += stu[i-1].y;28 LL s, Max;29 s = 1;30 Max = stu[1].y;31 for (int e=2; e<=n; e++)32 {33 while (stu[e].x - stu[s].x >= d && s <= e)34 s ++;35 Max = max (Max, stu[e].y - stu[s-1].y);36 }37 printf ("%I64d\n", Max);38 }39 return 0;40 }
题目链接：
C. Kefa and Park
题目描述：
有一个树，1节点是home，叶子节点是公园，在节点中可能会有猫，问从home出发在路上不能经过连续的m个猫，问能到达几个不同的公园？
解题思路：
先标记一下叶子节点，然后dfs这个树，统计共到达几个叶子节点，注意根节点度数为1的时候，也是比较水。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const int maxn = 100010; 8 struct node 9 {10 int to, next;11 } edge[maxn * 2];12 int head[maxn], arr[maxn], du[maxn], sum, tot, m;13 14 void Add (int from, int to)15 {16 edge[tot].to = to;17 edge[tot].next = head[from];18 head[from] = tot ++;19 }20 void dfs (int u, int fa, int num)21 {22 if (num > m)23 return;24 if (du[u] == 1 && u != 1)25 sum ++;26 for (int i=head[u]; i!=-1; i=edge[i].next)27 {28 int v = edge[i].to;29 if (fa != v)30 dfs (v, u, arr[v]==0?0:num+arr[v]);31 }32 }33 int main ()34 {35 int n;36 while (scanf ("%d %d", &n, &m) != EOF)37 {38 tot = 0;39 memset (head, -1, sizeof(head));40 memset (du, 0, sizeof(du));41 42 for (int i=1; i<=n; i++)43 scanf ("%d", &arr[i]);44 45 while (-- n)46 {47 int u, v;48 scanf ("%d %d", &u, &v);49 Add (u, v);50 Add (v, u);51 du[u] ++;52 du[v] ++;53 }54 55 sum = 0;56 dfs (1, 0, arr[1]);57 printf ("%d\n", sum);58 59 }60 return 0;61 }
题目链接：
D. Kefa and Dishes
题目描述：
一位顾客吃m道菜，每到菜都有一个满足度，对与特殊的菜(xi, yi)， 先吃xi再吃yi会再额外增加一个满足度ci，问m道不同的菜，最大满足度为多少？
解题思路：
由于数据范围[1, 18],很容易想到状压，一共pow(2, 18)种状态，然后dp[x][y], x代表当前已经选择的菜肴数目，y代表选择的最后一道菜，然后向下递推就好了。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 typedef __int64 LL; 8 const LL maxn = 270000; 9 LL dp[maxn][20], arr[20], maps[20][20];10 11 int judge (LL x)12 {13 int ans = 0;14 while (x)15 {16 if (x % 2)17 ans ++;18 x /= 2;19 }20 return ans;21 }22 int main ()23 {24 LL n, m, k;25 while (scanf ("%I64d %I64d %I64d", &n, &m, &k) != EOF)26 {27 LL u, v, x;28 memset (maps, 0, sizeof(maps));29 memset (dp, 0, sizeof(dp));30 for (int i=0; i
题目链接：
E. Kefa and Watch
题目描述：
给一字符串，有两个操作，
1 l r d：[l, r]区间内的所有的数改成d；
2 l r d: 判定[l, r]区间内的循环节是不是d；
解题思路：
hash + 线段树，修改的时候是区间修改，在线段树上操作效率会很可观。还有就是判定[l, r]区间的循环节是不是d， 只需要比较 [l, r-d] 和 [l+d, r] 是否相等，因为
在线段树上我们只需要对[l, r-d]与[l+d, r]进行hash，也就是对区间转化为求一个多项式的值，(多项式：sl*seed0 + sl+1*seed1 + sl+2*seed2 + ...... + sr*seedr-l+1)然后比较hash出来的值是不是相等即可。
在线段树上进行hash维护还是第一次见，还是值得絮叨絮叨，这个题目求这个多项式的值，相当于把区间转换为seed进制的数。所以seed要比s串中的字符要至少大1，s串很长的啊，所以为了防止int溢出我们可以对seed进制数进行取余，对什么取余呢，最好是孪生素数(1e9+7, 1e9+9)，不开心的话也可以是普通素数(冲突的概率会比较小)，当然也可以是其他的数(但是冲突的概率就不能保证了)。
这个题目也是ac的好心累，从wa3 改到 wa8，一怒之下全删从新再来，竟然对了，ORZ(怪我咯，怪我咯，这么优雅的题目被我写残成这样)
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 typedef __int64 LL; 8 #define rson 2*root+2 9 #define lson 2*root+1 10 const LL maxn = 100010; 11 const LL seed = 11; 12 const LL mod = 1000000007; 13 struct node 14 { 15 int l, r, len, lazy, hash; 16 int mid () 17 { 18 return (l + r) / 2; 19 } 20 } tree[maxn*4]; 21 int p[maxn], c[10][maxn]; 22 23 int merge (int hash1, int hash2, int len) 24 { 25 if (len > 0) 26 return ( (LL)hash1 * p[len] % mod + hash2 ) % mod; 27 return hash1; 28 } 29 30 void pushdown (int root) 31 { 32 int x = tree[root].lazy; 33 tree[root].lazy = -1; 34 tree[lson].lazy = tree[rson].lazy = x; 35 tree[lson].hash = c[x][tree[lson].len]; 36 tree[rson].hash = c[x][tree[rson].len]; 37 } 38 39 void build (int l, int r, int root) 40 { 41 tree[root].l = l; 42 tree[root].r = r; 43 tree[root].lazy = -1; 44 tree[root].len = r - l + 1; 45 if (l == r) 46 { 47 tree[root].hash = getchar() - '0'; 48 return ; 49 } 50 build (l, tree[root].mid(), lson); 51 build (tree[root].mid()+1, r, rson); 52 tree[root].hash = merge (tree[lson].hash, tree[rson].hash, tree[rson].len); 53 } 54 55 void update (int l, int r, int x, int root) 56 { 57 if (l > r) 58 return ; 59 if (tree[root].l==l && tree[root].r==r) 60 { 61 tree[root].lazy = x; 62 tree[root].hash = c[x][tree[root].len]; 63 return ; 64 } 65 if (tree[root].lazy != -1) 66 pushdown (root); 67 int mid = tree[root].mid(); 68 update (l, min(mid, r), x, lson); 69 update (max(mid+1, l), r, x, rson); 70 tree[root].hash = merge (tree[lson].hash, tree[rson].hash, tree[rson].len); 71 72 } 73 74 int query (int l, int r, int root) 75 { 76 if (l > r) 77 return 0; 78 if (l==tree[root].l && r==tree[root].r) 79 return tree[root].hash; 80 if (tree[root].lazy != -1) 81 pushdown (root); 82 int mid = tree[root].mid(); 83 return merge(query (l, min(mid, r), lson), query (max(mid+1, l), r, rson), r - max(mid+1, l) + 1); 84 } 85 86 int main () 87 { 88 int n, m, k; 89 while (scanf ("%d %d %d", &n, &m, &k) != EOF) 90 { 91 p[0] = 1; 92 for (int i=1; i<=n; i++) 93 p[i] = (LL)p[i-1] * seed % mod; 94 for (int i=0; i<10; i++) 95 for (int j=1; j<=n; j++) 96 c[i][j] = (c[i][j-1] + (LL)i*p[j-1] % mod) % mod; 97 98 m += k; 99 getchar ();100 build (1, n, 0);101 102 while (m --)103 {104 int op, l, r, d;105 106 scanf ("%d %d %d %d", &op, &l, &r, &d);107 if (op == 1)108 update (l, r, d, 0);109 else110 printf ("%s\n", query (l+d, r, 0)==query(l, r-d, 0) ? "YES":"NO");111 }112 113 }114 return 0;115 }