2017 ZSTU寒假排位赛 #4

　　题目链接：https://vjudge.net/contest/148543#overview。

　　A题：n个罪犯，每个人有一个犯罪值，现在要从里面选出连续的c个人，每个人的犯罪值都不能超过t，问选法的种类数。O(n)xjbg一下即可：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <map>

 #include <set>

 #include <vector>

 #include <queue>

 #include <iostream>

 using namespace std;

 const int N =  + ;

 typedef long long ll;

 typedef pair<int,int> pii;

 int a[N];

 int main()

 {

     int n,t,c;

     cin >> n >> t >> c;

     ll ans = ;

     int cnt = ;

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

     {

         int temp;scanf("%d",&temp);

         if(temp <= t) cnt++;

         else

         {

             if(cnt >= c) ans += cnt - c + ;

             cnt = ;

         }

     }

     if(cnt >= c) ans += cnt - c + ;

     cout << ans << endl;

     return ;

 }

　　B题：n个数字，从中选出不重叠的k段数字，每段的长度都为m，问最大的和。因为n是5000，所以很明显的开个二维数组n方dp一下即可：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <map>

 #include <set>

 #include <vector>

 #include <queue>

 #include <iostream>

 using namespace std;

 const int N =  + ;

 typedef long long ll;

 typedef pair<int,int> pii;

 ll pre[N];

 ll dp[N][N];

 int main()

 {

     int n,m,k;

     cin >> n >> m >> k;

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

     {

         int x;

         scanf("%d",&x);

         pre[i] = pre[i-] + x;

     }

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

     {

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

         {

             dp[i][j] = max(dp[i-][j], dp[i-m][j-] + pre[i] - pre[i-m]);

         }

     }

     cout << dp[n][k] << endl;

     return ;

 }

　　C题：给一个距离矩阵，问是否可能构成一棵树。做法是克鲁斯卡尔以后dfs一遍看看距离矩阵是否相等即可。仔细想想还是挺妙的。代码如下（写的有点挫）：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <map>

 #include <set>

 #include <vector>

 #include <queue>

 #include <iostream>

 using namespace std;

 const int N =  + ;

 typedef long long ll;

 typedef pair<int,int> pii;

 int root[N],cnt,vis[N],last[N];

 int n,G[N][N],d[N][N];

 vector<pii> graph[N];

 void init() {for(int i=;i<=n;i++) root[i] = i;}

 int find(int x) {return x == root[x] ? x : root[x] = find(root[x]);}

 void connect(int x,int y,int w)

 {

     int rx = find(x);

     int ry = find(y);

     if(rx != ry)

     {

         root[rx] = ry;

         //d[x][y] = d[y][x] = w;

         graph[x].push_back(pii(y,w));

         graph[y].push_back(pii(x,w));

         cnt--;

     }

 }

 struct edge

 {

     int u,v,w;

     bool operator < (const edge & temp) const

     {

         return w > temp.w;

     }

 };

 void dfs(int u,int fa)

 {

     for(int i=;i<graph[u].size();i++)

     {

         pii p = graph[u][i];

         int v = p.first;

         int w = p.second;

         if(v == fa) continue;

         last[v] = last[u] + w;

         dfs(v,u);

     }

 }

 int main()

 {

     scanf("%d",&n);

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

     {

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

         {

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

             if(i == j && G[i][j]) return *puts("NO");

         }

     }

     for(int i=;i<=n;i++) for(int j=;j<=n;j++) if(G[i][j] != G[j][i] || i!=j && G[i][j] == ) return *puts("NO");

     priority_queue<edge> Q;

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

     {

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

         {

             Q.push((edge){i,j,G[i][j]});

         }

     }

     cnt = n; init();

     for(;cnt > ;)

     {

         edge e = Q.top();Q.pop();

         connect(e.u, e.v, e.w);

     }

     //for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) printf("%d%c",d[i][j],j==n?'\n':' ');

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

     {

         last[i] = ;

         dfs(i,-);

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

         {

             if(j == i) continue;

             if(last[j] != G[i][j]) return *puts("NO");

         }

     }

     puts("YES");

     return ;

 }

　　D题：给两个部分的字符串，分别重复n次和m次（最终长度相等），问有多少位置字符是不同的。只需要比较一个lcm里面的长度是肯定的，但暴力做肯定T。一个lcm中，考虑到只有pos%gcd这些位置需要比较。那么就可以线性的做出来了。最后扩大相应倍数即可。代码如下：

 #include <stdio.h>

 #include <algorithm>

 #include <string.h>

 #include <map>

 #include <set>

 #include <vector>

 #include <queue>

 #include <iostream>

 using namespace std;

 const int N =  + ;

 typedef long long ll;

 typedef pair<int,int> pii;

 ll n,m;

 char a[N],b[N];

 int vis[N][];

 int main()

 {

     cin >> n >> m;

     scanf("%s%s",a+,b+);

     int lena = strlen(a+);

     int lenb = strlen(b+);

     int g = __gcd(lena,lenb);

     ll lcm = (ll)lena / g * lenb;

     ll ans = ;

     for(int i=;i<=lena;i++) vis[i%g][a[i]-'a']++;

     for(int i=;i<=lenb;i++) ans += vis[i%g][b[i]-'a'];

     cout << 1LL*lena * n / lcm * (lcm - ans) << endl;

     return ;

 }

　　E题，看了一会没怎么明白题意，暂时放过吧。

巴特西

2017 ZSTU寒假排位赛 #4

最新文章

热门文章