A
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};
const int mod = 1e9 + ;
const int gakki = + + + + 1e9;
const int N = 2e5 + ;
bool ok(string x)
{
int len = x.size();
if (len == )
{
return true;
}
for (int i = ; i < x.size() / ; i++)
{
if (x[i] != x[x.size() - - i])
{
return false;
}
}
return true;
}
int main()
{
ios_base::sync_with_stdio();
cin.tie();
string a;
cin >> a;
int flag = ;
while (flag)
{
if (ok(a))
{
if (a.size() == )
{
cout << << endl;
return ;
}
a = a.substr(, a.size() - );
}
else
{
flag = ;
}
}
cout << a.size() << endl;
return ;
}
B
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};
const int mod = 1e9 + ;
const int gakki = + + + + 1e9;
const int N = 2e5 + ;
map<int,ll> mp;
int main()
{
ios_base::sync_with_stdio();
cin.tie();
ll anser=;
int n,m;
cin >> n;
int a,b;
for(int i=;i<=n;i++)
{
cin >> a >> b;
if(mp[a]<b)
{
anser+=b-mp[a];
mp[a]=b;
}
}
cin >> m;
for(int i=;i<=m;i++)
{
cin >> a >> b;
if(mp[a]<b)
{
anser+=b-mp[a];
mp[a]=b;
}
}
cout<<anser<<endl;
return ;
}
C
解:
构造题
很明显如果是有不小于一个的度大于2的点则No
如果没有度大于2的点则是一条链 直接输出两端 如果有的话则是菊花图 找每个度为1的叶子点与中心相连
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};
const int mod = 1e9 + ;
const int gakki = + + + + 1e9;
const int N = 1e5 + ;
vector<int> g[N];
int du[N];
int main()
{
ios_base::sync_with_stdio();
cin.tie();
int n;
cin >> n;
int u, v;
for (int i = ; i < n; i++)
{
cin >> u >> v;
g[u].pb(v), g[v].pb(u);
du[u]++, du[v]++;
}
int sum = ;
int maxn = -;
int aim = ;
for (int i = ; i <= n; i++)
{
if (du[i] > )
{
sum++;
}
if (du[i] > maxn)
{
aim = i;
maxn = du[i];
}
}
if (sum > )
{
cout << "No" << endl;
return ;
}
if (maxn > )
{
cout << "Yes" << endl;
int cnt=;
for(int i=;i<=n;i++)
{
if(du[i]==)
{
cnt++;
}
}
cout << cnt << endl;
for (int i = ; i <= n; i++)
{
if (i == aim)
{
continue;
}
if (du[i] == )
{
cout << aim << " " << i << endl;
}
}
}
else
{
cout << "Yes" << endl;
cout << << endl;
for (int i = ; i <= n; i++)
{
if (du[i] == )
{
cout << i << " ";
}
}
cout << endl;
}
return ;
}
D. Bookshelves
题意:
给你N个书K个书架,每个书有一个价值,要求你把书分成 连续的K段 分配进这K个书架使得这几个书架的总值 AND值 最大
解:
贪心 DP或者BFS
首先因为是AND操作所以我们要从最高位开始贪心 如果可行的话就 ans | =1 << i
DP:
/*Huyyt*/
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int dir[][] = {{, }, {, }, {, -}, { -, }, {, }, {, -}, { -, -}, { -, }};
const int mod = 1e9 + ;
const int gakki = + + + + 1e9;
const int N = + ;
int n, K;
ll sum[N][N];
ll a[N];
bool dp[N][N];
int main()
{
ios_base::sync_with_stdio();
cin.tie();
cin >> n >> K;
for (int i = ; i <= n; i++)
{
cin >> a[i];
sum[i][i] = a[i];
for (int j = i - ; j >= ; j--)
{
sum[j][i] = sum[j + ][i] + a[j];
}
}
//sum[i][j]表示从第i位到第j位的前缀和
ll ans = ;
for (int w = ; w >= ; w--) //从最高位开始贪起
{
mem(dp, ); //每一次要初始化
dp[][] = ; //dp[i][j]表示把前N个数分成j块每块都有 1<<w 是否可以
for (int i = ; i <= n; i++)
{
for (int j = i - ; j >= ; j--)
{
for (int k = ; k <= K; k++)
{
//如果从前的位置j满足可以分为k-1块而且从j+1到i的前缀和包含了之前贪心的答案同时1<<w位为1
if (dp[j][k - ] && (sum[j + ][i]&ans) == ans && ((sum[j + ][i] >> w) & ))
{
dp[i][k] = ;
}
}
}
}
if (dp[n][K])
{
ans |= 1LL << w;
}
}
cout << ans << endl;
return ;
}
BFS
E. Addition on Segments