Codeforces Round #302 (Div. 2)

A. Set of Strings

　　题意：能否把一个字符串划分为n段，且每段第一个字母都不相同？

　　思路：判断字符串中出现的字符种数，然后划分即可。

 #include<iostream>

 #include<set>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 char s[];

 set<char>st;

 int main()

 {

     int n;

     scanf("%d%s", &n,s);

     int len = strlen(s);

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

     {

         if (!st.count(s[i]))st.insert(s[i]);

     }

     if (st.size() < n) printf("NO\n");

     else

     {

         st.clear();

         printf("YES\n");

         int cur = ;

         while (n--)

         {

             st.insert(s[cur]);

             while (cur<len&&st.count(s[cur]))

             {

                 printf("%c", s[cur++]);

             }

             if (n == )

             {

                 while(cur<len) printf("%c", s[cur++]);

             }

             printf("\n");

         }

     }

     return ;

 }

B. Sea and Islands

　　题意：n*n的网格里都是水，现在需要填沙造出k个陆地，两两之间有边相邻的看成一片陆地。

　　思路：讨论奇偶。

 #include<iostream>

 #include<cstdio>

 using namespace std;

 int main()

 {

     int n, k;

     scanf("%d%d", &n, &k);

     int maxs = n /  * n + n %  * (n + ) / ;

     if (k > maxs)printf("NO\n");

     else

     {

         printf("YES\n");

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

         {

             int st;

             if (i % ==) st = ;

             else st = ;

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

             {

                 if ((j - st) %  == &&k>) printf("L"),k--;

                 else printf("S");

             }

             printf("\n");

         }

     }

     return ;

 }

C. Writing Code

　　题意：有n个程序员，现在需要合作完成m行的代码，要求最多只有b个bug,求总方案数？

　　思路：dp[i][j][k]:表示前i个程序员一起写j行代码bug数为k的方案数.采用滚动数组优化。

 #include<iostream>

 #include<cstdio>

 using namespace std;

 const int maxn = ;

 const int maxm = ;

 const int maxb = ;

 int dp[][maxm][maxb];//[i][j][k]表示前i个程序员一起写j行代码bug数为k的方案数

 int bugs[maxn];

 int main()

 {

     int n, m, b, mod;

     scanf("%d%d%d%d", &n, &m, &b, &mod);

     for (int i = ; i <= n; i++) scanf("%d", bugs + i);

     dp[][][] = dp[][][] = ;

     int pre, now;

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

     {

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

         {

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

             {

                 pre = ((i - ) & ),now=(i&);

                 if (k >= bugs[i]) dp[now][j][k] = (dp[pre][j][k] + dp[now][j - ][k - bugs[i]]) % mod;

                 else dp[now][j][k] = dp[pre][j][k];

             }

         }

     }

     int ans = ;

     for (int i = ; i <= b; i++) ans = (ans + dp[now][m][i]) % mod;

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

     return ;

 }

D. Destroying Roads

　　题意：有n个点，m条无向边。在保证s1到t1不超过l1小时、s2到t2不超过l2小时(每走一条边花费1小时)的情况下，求最多可以删去多少条边？

　　思路：求出每两点之间的最短距离，然后2层循环枚举重复的路径。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<queue>

 #include<cstring>

 using namespace std;

 const int maxn = ;

 struct edge

 {

     int next, to;

     edge(int tt=,int nn=):to(tt),next(nn){}

 };

 edge Edge[maxn*maxn];

 int Head[maxn], totedge;

 void addedge(int from, int to)

 {

     Edge[totedge] = edge(to, Head[from]);

     Head[from] = totedge++;

     Edge[totedge] = edge(from, Head[to]);

     Head[to] = totedge++;

 }

 int dis[maxn][maxn];

 bool vis[maxn];

 const int INF = 0x3f3f3f3f;

 int n, m;

 void SPFA(int st)

 {

     for (int i = ; i <= n; i++) dis[st][i] = INF;

     dis[st][st] = ;

     vis[st] = true;

     queue<int>q;

     q.push(st);

     while (!q.empty())

     {

         int u = q.front();

         q.pop();

         vis[u] = false;

         for (int i = Head[u]; i != -; i = Edge[i].next)

         {

             int v = Edge[i].to;

             if (dis[st][v] > dis[st][u] + )

             {

                 dis[st][v] = dis[st][u] + ;

                 if (!vis[v])

                 {

                     vis[v] = true;

                     q.push(v);

                 }

             }

         }

     }

 }

 int main()

 {

     scanf("%d%d", &n, &m);

     memset(Head, -, sizeof(Head));

     totedge = ;

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

     {

         int u, v;

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

         addedge(u, v);

     }

     int s1, d1, l1, s2, d2, l2;

     scanf("%d%d%d%d%d%d", &s1, &d1, &l1, &s2, &d2, &l2);

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

     if (dis[s1][d1] > l1 || dis[s2][d2] > l2) printf("-1\n");

     else

     {

         int minnum = dis[s1][d1] + dis[s2][d2];

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

         {

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

             {

                 if (dis[s1][i] + dis[i][j] + dis[j][d1] <= l1 && dis[s2][i] + dis[i][j] + dis[j][d2] <= l2)

                 {

                     minnum = min(minnum, dis[s1][i] + dis[i][j] + dis[j][d1] + dis[s2][i] + dis[j][d2]);

                 }

                 if (dis[s1][i] + dis[i][j] + dis[j][d1] <= l1 && dis[s2][j] + dis[j][i] + dis[i][d2] <= l2)

                 {

                     minnum = min(minnum, dis[s1][i] + dis[i][j] + dis[j][d1] + dis[s2][j] + dis[i][d2]);

                 }

                 if (dis[s1][j] + dis[j][i] + dis[i][d1] <= l1 && dis[s2][i] + dis[i][j] + dis[j][d2] <= l2)

                 {

                     minnum = min(minnum, dis[s1][j] + dis[j][i] + dis[i][d1] + dis[s2][i] + dis[j][d2]);

                 }

                 if (dis[s1][j] + dis[j][i] + dis[i][d1] <= l1 && dis[s2][j] + dis[j][i] + dis[i][d2] <= l2)

                 {

                     minnum = min(minnum, dis[s1][j] + dis[j][i] + dis[i][d1] + dis[s2][j] + dis[i][d2]);

                 }

             }

         }

         printf("%d\n", m - minnum);

     }

     return ;

 }

E. Remembering Strings

　　题意：有n个字符串，每个字符串m位，要使得每个字符串存在一个位置i上的字符唯一(其他字符串该位上的字符与该字符串不同，称为易记字符串)，你可以将某个字符串某位替换成任意字符，给出每个字符串每位替换的代价，求最小代价？

　　思路：将n个字符串各自是否为易记标记为0/1，则我们可以进行状态压缩，对每个当前的状态，找到最低位的0(表示该字符串进行转换，其余高位的0无需转换)，按照以下策略进行替换：如果该位唯一，则dp[i | (1 << j)] = dp[i]，否则考虑2种方案：第一种方案，直接让该位字符唯一——dp[i | (1 << j)] = min(dp[i | (1 << j)], dp[i] + cost[j][k])；第二种方案，找到所有和该字符串该位字符一样的所有字符串，除去代价最大的，其他字符串进行转换——dp[i | tmp] = min(dp[i | tmp], dp[i] + sumc - maxc)。

　　初始化为-1时需要考虑当前状态在此前是否已被转换到，没有则跳过；初始化为INF则不用考虑。

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 char str[][];

 int cost[][];

 const int maxc =  << ;//最大状态数

 int dp[maxc];

 int main()

 {

     int n, m;

     scanf("%d%d", &n, &m);

     for (int i = ; i < n; i++) scanf("%s", str + i);

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

     {

         for (int j = ; j < m; j++) scanf("%d", &cost[i][j]);

     }

     int total = ( << n) - ;//最终状态为111...11,n个1表示n个字符串都为易记

     memset(dp, -, sizeof(dp));

     dp[] = ;

     for (int i = ; i <total; i++)//枚举状态

     {

         if (dp[i] == -) continue;//该状态没有被转移到，跳过

         int j = ;

         while (((i >> j) & ) == ) j++;//找到该状态中为非易记的字符串进行状态转移

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

         {//让该字符串第k位的字符唯一

             int cnt = , sumc = , maxc = , tmp = ;

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

             {

                 if (str[z][k] == str[j][k])

                 {

                     cnt++;

                     sumc += cost[z][k];//总代价

                     maxc = max(maxc, cost[z][k]);//最大代价

                     tmp |= ( << z);//所有和该字符串该位一样的字符串为易记时的状态

                 }

             }

             if (cnt == )//如果该位字符本就唯一

             {

                 if (dp[i | ( << j)] == -)dp[i | ( << j)] = dp[i];

                 else dp[i | ( << j)] = min(dp[i | ( << j)], dp[i]);

             }

             else//否则

             {

                 //第一种方案，直接让该位字符唯一

                 if (dp[i | ( << j)] == -) dp[i | ( << j)] = dp[i] + cost[j][k];

                 else dp[i | ( << j)] = min(dp[i | ( << j)], dp[i] + cost[j][k]);

                 //第二种方案，找到所有和该字符串该位字符一样的所有字符串，除去代价最大的，其他字符串进行转换

                 if (dp[i | tmp] == -) dp[i | tmp] = dp[i] + sumc - maxc;

                 else dp[i | tmp] = min(dp[i | tmp], dp[i] + sumc - maxc);

             }

         }

     }

     printf("%d\n", dp[total]);

     return ;

 }

巴特西

Codeforces Round #302 (Div. 2)

最新文章

热门文章