T1.传送门
$\quad$ 读入倒序输出
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n ; cin>>n;
for(int i = n ; i >= 1 ; i --)cout<<i<<' ';
cout<<endl;
return 0;
}
T2.传送门
$\quad$因为是考虑子串,假如目前考虑多个子串相同,而每个子串又由相同字符组成,那么就变成了考虑字符相同问题。就是如何操作使得某一字符最多。
$\quad$枚举,所有大小写字符,每次考虑能否在有限的长度之内把操作数用完,假如多余了操作数,则需要单独计算,当多出的操作$ op == 1$ 时,损失一个字符,当多出的操作$ op > 1 $时,可以再操作回来。
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong()
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=5e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
void solve()
{
int n ; cin>>n;
string a , b , c;
vector<string>mx;
cin>>a>>b>>c;
mx.push_back(a);
mx.push_back(b);
mx.push_back(c);
int len = (int)a.length();
if( n >= len )cout<<"D"<<endl;
else
{
int x = n , y = n , z = n ;
for(int i = 0 ; i < 3 ; i ++)
{
int res = 0 ;
vector<int>cnt(26);
for(auto c : mx[i])
if(c >= 'a' && c <= 'z')cnt[c - 'a']++;
for(int k = 0 ; k < 26 ; k ++)
{
if(len - cnt[k] > 0)res = max(res , min(cnt[k] + n , len));
else res = max(res , len - (n == 1));
}
for(int k = 0 ; k < 26 ; k ++)cnt[k] = 0 ;
for(auto c : mx[i])
if( c >= 'A' && c <= 'Z')cnt[c - 'A'] ++;
for(int k = 0 ; k < 26 ; k ++)
{
if(len - cnt[k] > 0)res = max(res , min(cnt[k] + n , len));
else res = max(res , len - (n == 1));
}
//maxv + ( maxv - ( n - maxv) ) + n - maxv;
if( i == 0) x = res;
if( i == 1) y = res;
if( i == 2) z = res;
}
// cout<<x<<' '<<y<<' '<<z<<endl;
if(x > y && x > z )cout<<"A"<<endl;
else if(y > x && y > z)cout<<"B"<<endl;
else if(z > x && z > y)cout<<"C"<<endl;
else cout<<"D"<<endl;
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
#endif
solve();
return 0;
}
T3.传送门
$\quad$由于是点对问题,还是集合和集合的问题,因此考虑做差。真实的答案就是,总点对数 $ - $ 无效点对数。
$\quad$无效点对数 $ = $ $ x $ 的 子树(包含$ x $本身)$ * $ $ y $ 的子树。
$\quad$如何求子树大小呢?以$x$为根,求递归求出子树大小即可。以$x$为子树是为了比较方便的,判断出方向,以及和节点$y$之间的关系。
#include<bits/stdc++.h>
#pragma optimize(2)
#define endl '\n'
#define ll() to_ullong()
#define string() to_string()
#define Endl endl
using namespace std;
typedef long long ll;
typedef pair<int,int>PII;
typedef unsigned long long ull;
const int M=2010;
const int P=13331;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e6+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
int e[N], ne[N], idx,h[N];
void add(int a , int b )
{
e[idx] = b ,ne[idx] = h[a], h[a] = idx++;
}
bool st[N];
int sz[N] , n , x , y;
void dfs(int u , int fa)
{
st[u] = ( u == y) ;
sz[u] = 1;
for(int i = h[u] ; ~i ; i =ne[i])
{
int j = e[i];
if(j != fa)
{
dfs( j , u );
sz[u] += sz[j];
st[u] |= st[j];
}
}
}
void solve()
{
cin>>n>>x>>y;
memset(h , -1 , sizeof h);
for(int i = 1 ; i < n ; i++)
{
int a , b;
cin>>a>>b;
add(a , b ),add(b , a);
}
long long ans = 0 ;
dfs(x , -1 );
for(int i = h[x] ; ~i ; i = ne[i])
if(st[e[i]])
{
ans = 1ll * n * ( n - 1 ) - 1ll * (n - sz[e[i]]) * sz[y] ;
}
cout<<ans<<endl;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
#endif
solve();
return 0;
}