Codeforces Round #321 (Div. 2) A, B, C, D, E

题目链接：

　　A. Kefa and First Steps

题意描述：

　　给出一个序列，求最长不降连续子序列多长？

解题思路：

　　水题，签到

代码：

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 int main ()

 {

     int e, s, num, n, Max;

     while (scanf ("%d", &n) != EOF)

     {

         scanf ("%d", &s);

         n --, num = Max = ;

         while (n --)

         {

             scanf ("%d", &e);

             if (s <= e)

                 num ++;

             else

                 {

                     Max = max (Max, num);

                     num = ;

                 }

             swap (s, e);

         }

         printf ("%d\n", max (Max, num));

     }

     return ;

 }

580B. Kefa and Company

题目链接：

　　B. Kefa and Company

题目描述：

　　一群人去参加庆祝趴，每个人都有两个属性(贡献，身价)，在庆祝趴里面身价最大的和身价最小的差值不能大于等于d，问庆祝趴内所有人的总贡献最大为多少？

解题思路：

　　排序 + 取尺，先按照身价升序sort一下，然后设置两个指针取尺就好。

代码：

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef __int64 LL;

 const int maxn = ;

 struct node

 {

     LL x, y;

 }stu[maxn];

 bool cmp (node a, node b)

 {

     return a.x < b.x;

 }

 int main ()

 {

     LL n, d;

     while (scanf ("%I64d %I64d", &n, &d) != EOF)

     {

         stu[].x = stu[].y = ;

         for (int i=; i<=n; i++)

             scanf ("%I64d %I64d", &stu[i].x, &stu[i].y);

         sort (stu+, stu+n+, cmp);

         for (int i=; i<=n; i++)

             stu[i].y += stu[i-].y;

         LL s, Max;

         s = ;

         Max = stu[].y;

         for (int e=; e<=n; e++)

         {

              while (stu[e].x - stu[s].x >= d && s <= e)

                 s ++;

             Max = max (Max, stu[e].y - stu[s-].y);

         }

         printf ("%I64d\n", Max);

     }

     return ;

 }

580C. Kefa and Park

题目链接：

　　C. Kefa and Park

题目描述：

　　有一个树，1节点是home，叶子节点是公园，在节点中可能会有猫，问从home出发在路上不能经过连续的m个猫，问能到达几个不同的公园？

解题思路：

　　先标记一下叶子节点，然后dfs这个树，统计共到达几个叶子节点，注意根节点度数为1的时候，也是比较水。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int maxn = ;

 struct node

 {

     int to, next;

 } edge[maxn * ];

 int head[maxn], arr[maxn], du[maxn], sum, tot, m;

 void Add (int from, int to)

 {

     edge[tot].to = to;

     edge[tot].next = head[from];

     head[from] = tot ++;

 }

 void dfs (int u, int fa, int num)

 {

     if (num > m)

         return;

     if (du[u] ==  && u != )

         sum ++;

     for (int i=head[u]; i!=-; i=edge[i].next)

     {

         int v = edge[i].to;

         if (fa != v)

             dfs (v, u, arr[v]==?:num+arr[v]);

     }

 }

 int main ()

 {

     int n;

     while (scanf ("%d %d", &n, &m) != EOF)

     {

         tot = ;

         memset (head, -, sizeof(head));

         memset (du, , sizeof(du));

         for (int i=; i<=n; i++)

             scanf ("%d", &arr[i]);

         while (-- n)

         {

             int u, v;

             scanf ("%d %d", &u, &v);

             Add (u, v);

             Add (v, u);

             du[u] ++;

             du[v] ++;

         }

         sum = ;

         dfs (, , arr[]);

         printf ("%d\n", sum);

     }

     return ;

 }

580D. Kefa and Dishes

题目链接：

　　D. Kefa and Dishes

题目描述：

　　一位顾客吃m道菜，每到菜都有一个满足度，对与特殊的菜(xi, yi)，先吃xi再吃yi会再额外增加一个满足度ci，问m道不同的菜，最大满足度为多少？

解题思路：

　　由于数据范围[1, 18],很容易想到状压，一共pow(2, 18)种状态，然后dp[x][y], x代表当前已经选择的菜肴数目，y代表选择的最后一道菜，然后向下递推就好了。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef __int64 LL;

 const LL maxn = ;

 LL dp[maxn][], arr[], maps[][];

 int judge (LL x)

 {

     int ans = ;

     while (x)

     {

         if (x % )

             ans ++;

         x /= ;

     }

     return ans;

 }

 int main ()

 {

     LL n, m, k;

     while (scanf ("%I64d %I64d %I64d", &n, &m, &k) != EOF)

     {

         LL u, v, x;

         memset (maps, , sizeof(maps));

         memset (dp, , sizeof(dp));

         for (int i=; i<n; i++)

         {

             scanf ("%I64d", &arr[i]);

             dp[<<i][i] = arr[i];

         }

         for (int i=; i<k; i++)

         {

             scanf ("%I64d %I64d %I64d", &u, &v, &x);

             maps[u-][v-] = x;

         }

         LL ans = ;

         for (int i=; i<=(<<n); i++)

         {

             //当前吃掉的状态

             for (int j=; j<n; j++)

             {

                 //当前最后一个吃掉的物品编号

                 if (i & (<<j))

                 {

                     for (k=; k<n; k++)

                     {

                         //加入最后一个物品

                         if (i & (<<k))

                             continue;

                         dp[i|(<<k)][k] = max (dp[i|(<<k)][k], dp[i][j]+arr[k]+maps[j][k]);

                     }

                 }

                 if (judge(i) == m)

                     ans = max (ans, dp[i][j]);

             }

         }

         printf ("%I64d\n", ans);

     }

     return ;

 }

580E. Kefa and Watch

题目链接：

　　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，也就是对区间转化为求一个多项式的值，(多项式：s_l*seed⁰ + s_l+1*seed¹+ s_l+2*seed²+ ...... + sr*seed^r-l+1)然后比较hash出来的值是不是相等即可。

　　在线段树上进行hash维护还是第一次见，还是值得絮叨絮叨，这个题目求这个多项式的值，相当于把区间转换为seed进制的数。所以seed要比s串中的字符要至少大1，s串很长的啊，所以为了防止int溢出我们可以对seed进制数进行取余，对什么取余呢，最好是孪生素数(1e9+7, 1e9+9)，不开心的话也可以是普通素数(冲突的概率会比较小)，当然也可以是其他的数(但是冲突的概率就不能保证了)。

　　这个题目也是ac的好心累，从wa3 改到 wa8，一怒之下全删从新再来，竟然对了，ORZ(怪我咯，怪我咯，这么优雅的题目被我写残成这样)

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 typedef __int64 LL;

 #define rson 2*root+2

 #define lson 2*root+1

 const LL maxn = ;

 const LL seed = ;

 const LL mod = ;

 struct node

 {

     int l, r, len, lazy, hash;

     int mid ()

     {

         return (l + r) / ;

     }

 } tree[maxn*];

 int p[maxn], c[][maxn];

 int merge (int hash1, int hash2, int len)

 {

     if (len > )

         return ( (LL)hash1 * p[len] % mod + hash2 ) % mod;

     return hash1;

 }

 void pushdown (int root)

 {

     int x = tree[root].lazy;

     tree[root].lazy = -;

     tree[lson].lazy = tree[rson].lazy = x;

     tree[lson].hash = c[x][tree[lson].len];

     tree[rson].hash = c[x][tree[rson].len];

 }

 void build (int l, int r, int root)

 {

     tree[root].l = l;

     tree[root].r = r;

     tree[root].lazy = -;

     tree[root].len = r - l + ;

     if (l == r)

     {

         tree[root].hash = getchar() - '';

         return ;

     }

     build (l, tree[root].mid(), lson);

     build (tree[root].mid()+, r, rson);

     tree[root].hash = merge (tree[lson].hash, tree[rson].hash, tree[rson].len);

 }

 void update (int l, int r, int x, int root)

 {

     if (l > r)

         return ;

     if (tree[root].l==l && tree[root].r==r)

     {

         tree[root].lazy = x;

         tree[root].hash = c[x][tree[root].len];

         return ;

     }

     if (tree[root].lazy != -)

         pushdown (root);

     int mid = tree[root].mid();

     update (l, min(mid, r), x, lson);

     update (max(mid+, l), r, x, rson);

     tree[root].hash = merge (tree[lson].hash, tree[rson].hash, tree[rson].len);

 }

 int query (int l, int r, int root)

 {

     if (l > r)

         return ;

     if (l==tree[root].l && r==tree[root].r)

         return tree[root].hash;

     if (tree[root].lazy != -)

         pushdown (root);

     int mid = tree[root].mid();

     return merge(query (l, min(mid, r), lson), query (max(mid+, l), r, rson), r - max(mid+, l) + );

 }

 int main ()

 {

     int n, m, k;

     while (scanf ("%d %d %d", &n, &m, &k) != EOF)

     {

         p[] = ;

         for (int i=; i<=n; i++)

             p[i] = (LL)p[i-] * seed % mod;

         for (int i=; i<; i++)

             for (int j=; j<=n; j++)

                 c[i][j] = (c[i][j-] + (LL)i*p[j-] % mod) % mod;

         m += k;

         getchar ();

         build (, n, );

         while (m --)

         {

             int op, l, r, d;

             scanf ("%d %d %d %d", &op, &l, &r, &d);

             if (op == )

                 update (l, r, d, );

             else

                 printf ("%s\n", query (l+d, r, )==query(l, r-d, ) ? "YES":"NO");

         }

     }

     return ;

 }

巴特西

Codeforces Round #321 (Div. 2) A, B, C, D, E

最新文章

热门文章