“美登杯”

小花梨的字符串

 

解释

因为要满足min(strlen(a),strlen(b))-1,所以如果是第1个到第2个就是a，b，ab；如果是第一个到第三个就是，a; ab，b;abc， bc,c每次都是其字串，所以1+2+···+n,n是其中的个数

#include<iostream>
#include <cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
char a[10001];

int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    scanf("%s",a);
    for(int i=0;i<m;i++){
        int l,r;
        cin>>l>>r;
        printf("%d\n",(r-l+1)*(r-l+2)/2);
    }
    return 0;
}

小花梨判连通

题解

直接对每个连通块进行染色即可。如果两个点在k张图中都是连通的，说明这两个点在k张图中的颜色都是一样的。

必备知识

string s("hello,world");
decltype(s.size()) punct_cnt=0;//decltype也是c++11特性，用于选择和返回操作数的数据类型。
for(auto c:s)//对于s中的每个字符
if(ispunct(c))
++punct_cnt;

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
int n, k, nowcolor;
vector<int>color[maxn];
vector<int>G[maxn];
bool vis[maxn];
map<vector<int>, int>Map;
void dfs(int u)
{
    vis[u] = 1;color[u].push_back(nowcolor);
    for(auto v : G[u])if(!vis[v])dfs(v);
}
int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= k; i++)
    {
        for(int j = 1; j <= n; j++)G[j].clear(), vis[j] = 0;
        int m, u, v;
        scanf("%d", &m);
        while(m--)
        {
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        nowcolor = 0;
        for(int j = 1; j <= n; j++)
            if(!vis[j])nowcolor++, dfs(j);
    }
    for(int i = 1; i <= n; i++)Map[color[i]]++;
    for(int i = 1; i <= n; i++)printf("%d\n", Map[color[i]]);
    return 0;
}