A. Theramore
题意：
给定一个01串，可以选择一个奇数长度的区间，使得该区间翻转，求任意次数操作后的最小字典序。
分析：
我们发现不管怎么转，奇数位置上的数永远在奇数上，偶数永远还在偶数上，但是我们可以通过翻转随意的去更换位置，因此我们只需要统计处奇偶上01的位
置，然后把1尽可能的往后排即可。
#include <iostream>
#include <cstring>
using namespace std;
char s[100010];
int c[2][2];
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
memset(c, 0, sizeof c);
scanf("%s", s + 1);
for (int i = 1; s[i]; i++)
c[s[i] - '0'][i & 1]++;
for (int i = 1; s[i]; i++)
{
if (c[0][i & 1]) c[0][i & 1]--, printf("0");
else printf("1");
}
puts("");
}
return 0;
}
D. Quel'Thalas
题意：
求出最少的线条覆盖n*n的矩阵。
分析：
横竖都来n条，输出2n即可。
#include <iostream>
using namespace std;
int main()
{
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
cout << (n << 1) << '\n';
}
return 0;
}
G. Darnassus
题意：
给定一个长度为n的序列a,是有1-n的排列组成，连接i j两个点的代价为abs(i - j) * abs(a[i] - a[j])，求其最小生成树。
分析：
这个题的思考方式很独特
如果我们依次连接 i 和 i+1 会发现 abs(i-j) 这一项就消掉了
因为序列a是排列 所以 abs(a[i]-a[j])≤n-1
也就是说只需要知道边权≤n-1即可
|a[i]-a[j]|*|i-j|≤n-1
我们每个点 i 开始枚举向后扩展sq=sqrt(n)这样可以使得 |i-j|≤sq
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n && j <= i + sq; j++) {
int w = abs(i - j) * abs(p[i] - p[j]);
if (w < n)e[w].push_back({ i, j });
}
}
但是也有可能|i-j|≥sq |a[i]-a[j]|≤sq的情况
同样需要枚举 |a[i]-a[j]|≤sq
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n && j <= i + sq; j++) {
int w = abs(i - j) * abs(pos[i] - pos[j]);//pos[p[i]] = i
if (w < n)e[w].push_back({ pos[i], pos[j] });
}
}
复杂度为O(n sqrt(n)) 再排个序就会炸掉 所以用个捅 储存边权等于w的所有边
namespace UF {
int fa[MAXN], rank[MAXN];
inline void init(int n)
{
for (int i = 1; i <= n; ++i)
{
fa[i] = i;
rank[i] = 1;
}
}
int find(int x)
{
return x == fa[x] ? x : (fa[x] = find(fa[x]));
}
inline void merge(int i, int j)
{
int x = find(i), y = find(j);
if (rank[x] <= rank[y])
fa[x] = y;
else
fa[y] = x;
if (rank[x] == rank[y] && x != y)
rank[y]++;
}
inline bool same(int i, int j) {
return find(i) == find(j);
}
}
int n;
int p[MAXN], pos[MAXN];
void slove() {
cin >> n;
UF::init(n);
for (int i = 1; i <= n; i++)cin >> p[i], pos[p[i]] = i;
vector<vector<pair<int, int>>>e(n);
for (int i = 2; i <= n; i++) {
int w = abs(p[i] - p[i - 1]);
e[w].push_back({ i - 1,i });
}
int sq = sqrt(n);
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n && j <= i + sq; j++) {
int w = abs(i - j) * abs(p[i] - p[j]);
if (w < n)e[w].push_back({ i, j });
}
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n && j <= i + sq; j++) {
int w = abs(i - j) * abs(pos[i] - pos[j]);
if (w < n)e[w].push_back({ pos[i], pos[j] });
}
}
ll ans = 0;
int cnt = n;
for (int w = 0; w <= n - 1; w++) {
for (auto p : e[w]) {
int u = p.first, v = p.second;
if (UF::same(u, v))continue;
UF::merge(u, v);
ans += w;
cnt--;
if (cnt == 1)goto END;
}
}
END:
cout << ans << endl;
}
H. Orgrimmar
题意：
给定一颗树，给你选择一些点，使得这些点，最多只有两个点直接有边相连。
做法：
显然的树上dp [树的最大独立集]
但是这个题目又有一点不一样 可以选最多一对相邻的两个点
所以dp也就要改变一点
f[u][0]表示u点没选
f[u][1]表示u点选了 并且子节点没有与之相连的点
f[u][2]表示u点选了 但是子节点中有与之相连的点
转移过程有点像皇宫看守
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,n;
const int N=5e5+10;
ll dp[N][3];
int h[N],e[N],ne[N],idx;
void add(int a,int b){
e[++idx]=b;
ne[idx]=h[a];
h[a]=idx;
}
void dfs(int u,int fa){
ll m0=0,m1=0,m2=-1e9;
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(j==fa) continue;
dfs(j,u);
m0+=max({dp[j][0],dp[j][1],dp[j][2]});
m1+=dp[j][0];
m2=max(dp[j][1]-dp[j][0],m2);
}
dp[u][0]=m0;
dp[u][1]=m1+1;
dp[u][2]=m1+m2+1;
}
void solve(){
scanf("%d",&n);
memset(h,-1,sizeof h);
memset(dp,0,sizeof dp);
idx=0;
for(int i=1;i<n;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b),add(b,a);
}
dfs(1,0);
printf("%d\n",max({dp[1][0],dp[1][1],dp[1][2]}));
}
int main()
{
int size(512<<20); // 512M
__asm__ ( "movq %0, %%rsp\n"::"r"((char*)malloc(size)+size));
scanf("%d",&t);
while(t--){
solve();
}
exit(0);
}
K. Stormwind
题意：
给定一个n*m的矩阵，要在其中画尽可能地线。
线满足地条件：
1、线的端点必须在矩阵地边界上。
2、线必须平行于至少一条边。
3、在画完后，每一块需为面积大于等于k的矩阵。
4、线不能有共同端点。
分析：
可以枚举切出来的矩阵的宽度，再算长度。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k,t;
void solve(){
cin>>n>>m>>k;
ll ans=0;
for(int i=1;i<=n&&i<=k;i++){
ll c;
if(k%i) c=k/i+1;
else c=k/i;
ll cnt=0;
if(m>=c){
cnt+=m/c-1;
cnt+=n/i-1;
ans=max(ans,cnt);
}
}
cout<<ans<<endl;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
cin>>t;
while(t--){
solve();
}
}