写在前面
此 时 无 声 胜 有 声
题解
A
好水啊，不知道为什么是一道蓝题，感觉顶多绿
首先，我们发现虽然(n)很大(20000)，但是每个字符的长度只有(10)，所以，我们可以枚举出每个字符串的连续子集。
然后开个(map)来存，之后再这题就做完了
#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 5;
int n;
map <string, int> cont; // 记录每一个连续子集出现过的次数
map <string, int> vis; // 记录是否在当前这个字符串中出现过
string s[N];
signed main () {
ios :: sync_with_stdio (false);
cin>>n;
for (int i = 1; i <= n; i++) {
cin>>s[i];
vis.clear (); // 清空
for (int j = 0; j <= s[i].size (); j++) {
for (int k = 1; j + k <= s[i].size (); k++) {
string ss = s[i].substr (j, k);
// s.substr(x,y)表示取s[j-j+k]位
if (!vis[ss]) {
vis[ss] = 1;
cont[ss] ++;
}
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
ans += cont[s[i]] - 1; // 因为每个人都可以试出自己的密码，所以每个都要减去1
}
printf ("%d
", ans);
return 0;
}
B
C
D
E
一眼题。
直接tarjan求出连通块，统计连通块最小值并记录就行了
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5, M = 3e5 + 5, mod = 1e9 + 7;
struct Node {
int next, to;
} edge[M];
int head[N], cnt;
inline int read () {
int tot = 0, f = 1; char c = getchar ();
while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar (); }
while (c >= '0' && c <= '9') { tot = tot * 10 + c - '0'; c = getchar (); }
return tot * f;
}
int dfn[N], low[N], deep, tot, color[N];
bool vis[N];
int st[N], top;
int n, m, val[N];
int minx[N], sum[N];
inline void add (int x, int y) {
edge[++cnt].next = head[x];
edge[cnt].to = y;
head[x] = cnt;
}
inline void tarjan (int u) {
dfn[u] = low[u] = ++ deep;
vis[u] = 1; st[++top] = u;
for (int i = head[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (!dfn[v]) {
tarjan (v);
low[u] = min (low[u], low[v]);
}
else {
if (vis[v]) low[u] = min (low[u], low[v]);
}
}
if (dfn[u] == low[u]) {
color[u] = ++tot;
vis[u] = 0;
while (st[top] != u) {
color[st[top]] = tot;
vis[st[top--]] = 0;
} top--;
}
}
signed main () {
n = read ();
for (int i = 1; i <= n; i++) val[i] = read (); m = read ();
for (int i = 1; i <= m; i++) {
int x = read (), y = read ();
add (x, y);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan (i);
// for (int i = 1; i <= n; i++) cout<<color[i]<<" "; cout<<endl;
memset (minx, 0x3f, sizeof (minx));
for (int i = 1; i <= n; i++) {
if (val[i] < minx[color[i]]) minx[color[i]] = val[i], sum[color[i]] = 1;
else if (val[i] == minx[color[i]]) sum[color[i]]++;
}
// cout<<sum[1]<<endl;
long long ans = minx[1], rans = sum[1];
for (int i = 2; i <= tot; i++) {
ans += minx[i];
rans *= sum[i]; rans %= mod;
}
printf ("%lld %lld
", ans, rans);
return 0;
}
F
我们可以将同一颜色的连通块缩成点。
然后我们就得到了一棵黑白相间的树。
树的直径的一半即为答案
ps：树的直径，先从随便一个点出发找到最远的点，再从最远的点走到这个点的最远的点，即为树的直径
#include <bits/stdc++.h>
using namespace std ;
const int MAXN = 200000 + 5 ;
int color[ MAXN ] , fa[ MAXN ] , n ;
struct Node {
int next , to , w ;
} edge[ MAXN << 1 ] ;
int head[ MAXN ] , cnt ;
inline int read () {
int tot = 0 , f = 1 ; char c = getchar () ;
while ( c < '0' || c > '9' ) { if ( c == '-' ) f = -1 ; c = getchar () ; }
while ( c >= '0' && c <= '9' ) { tot = tot * 10 + c - '0' ; c = getchar () ; }
return tot * f ;
}
inline void add ( int x , int y ) {
edge[ ++ cnt ].next = head[ x ] ;
edge[ cnt ].to = y ;
head[ x ] = cnt ;
}
inline int find ( int k ) {
if ( fa[ k ] == k ) return k ;
else return fa[ k ] = find ( fa[ k ] ) ;
}
int maxdeep , maxu ;
inline void dfs ( int deep , int u , int father ) {
if ( deep > maxdeep ) maxdeep = deep , maxu = u ;
for ( int i = head[ u ] ; i ; i = edge[ i ].next ) {
int v = edge[ i ].to ;
if ( v == father ) continue ;
dfs ( deep + 1 , v , u ) ;
}
}
int a[ MAXN ] , b[ MAXN ] ;
signed main () {
n = read () ;
for ( int i = 1 ; i <= n ; i ++ ) {
color[ i ] = read () ;
fa[ i ] = i ;
}
for ( int i = 1 ; i < n ; i ++ ) {
a[ i ] = read () ; b[ i ] = read () ;
int fx = find ( a[ i ] ) , fy = find ( b[ i ] ) ;
if ( color[ fx ] == color[ fy ] ) fa[ fx ] = fa[ fy ] ;
}
for ( int i = 1 ; i <= n ; i ++ )
fa[ i ] = find ( fa[ i ] ) ;
for ( int i = 1 ; i <= n ; i ++ )
if ( fa[ a[ i ] ] != fa[ b[ i ] ] )
add ( fa[ a[ i ] ] , fa[ b[ i ] ] ) , add ( fa[ b[ i ] ] , fa[ a[ i ] ] ) ;
dfs ( 0 , fa[ 1 ] , 0 ) ;
dfs ( 0 , maxu , 0 ) ;
printf ( "%d
" , ( maxdeep + 1 ) / 2 ) ;
}