1942D. Learning to Paint
题目大意：
给定一行白格子，可以将任意的格子染成黑色，最终形成多个黑色的连续段，对每个连续段[i,j]有一个权重（题目给定），为aij，每个染色方案的权值就是所有连续段的权值的和。要求所有染色方案中前k大的权值。
注意事项：
权重aij的范围是[-1e6,1e6]，格子个数n<=1000，前k大权值可以重复且保证k<=min(2n,5000)
思考：
如果直接考虑的话，本题的状态空间是所有的染色方案的权值，个数多达2n，肯定要砍掉其中一些不必要的，只考虑有可能成为前k大的染色方案。
但本题的aij没什么性质，只好在算法上优化。
考虑使用dp，将格子一个个放入，dp[i]表示考虑只对[1,i]这一段白格子进行染色，可以得到的前k大的权值。这样每次都只需要考虑最大的k个权值，其他的好多好多都没用啦！然后看一眼time limit：4.5s，稳啦！
然后转移的时候有个trick，就是将第k大权值看作“删除了前k-1大的权值后，最大的权值”，于是整个过程就变成了求k次最大权值，每次从候选人中选最大的，然后将那个元素删除，更新候选人集合。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,k,T;
const int N = 1010, M = 5e6+10;
multiset<int,greater<int> > ss[N];
int g[N][N];
typedef pair<int,int> pii;
std::multiset<int, std::greater<int>, std::allocator<int>>::iterator now[N];
int main()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>T;
while(T--)
{
cin>>n>>k;
for(int i = 1; i <= n; ++i)
for(int j = i; j <= n; ++j)
cin>>g[i][j];
vector<vector<int> > dp(n+1);
dp[0] = {0};
for(int i = 1; i <= n; ++i)
{
priority_queue<array<int,3> > q;
q.push({dp[i-1][0],i-1,0});
for(int j = i-2; ~j; --j)
q.push({dp[j][0]+g[j+2][i],j,0});
q.push({g[1][i],-1,0});
int cnt = 0;
while(cnt < k && q.size())
{
++cnt;
auto [num,j,id] = q.top();
q.pop();
dp[i].push_back(num);
if(j < 0 || id+1==dp[j].size()) continue;
q.push({dp[j][id+1]+(j == i-1 ? 0 : g[j+2][i]),j,id+1});
}
}
for(auto t: dp[n])
cout<<t<<' ';
cout<<'\n';
}
return 0;
}
一些实现上的细节：
1、dp[i]用vector来存储，不需要set
2、在维护的时候用priority_queue比set快
3、pq中存三元组 可以更高效地维护信息
1938J. There and Back Again
题目大意：
n个点m条边的无向图，每条边有一个正权值（距离），无重边或自环。给定源点和汇点，找两条不同的路使得路径长度总和最短，或声明不存在这样的两条路。
注意事项：
n ~ 1e5, m ~ 3e5; 两条路不同当且仅当其中所有边组成的集合（set，不是multiset）不同。
思考：
第一反应是寻找第k短路（但发现最短路与第二短路可能使用了相同的边集，不一定满足条件），于是重心便来到了：如何找到两个本质不同的道路，让他们尽可能小呢？
考虑：答案的两条路应该是什么样的？
然后就发现：（如果存在这样的两条路）最短路一定是在答案的两条路中的！可以用调整法显然证明
那么我们已经固定了一条路，找另一条和他本质不同的路就比较方便了。
我们先找一条最短路（或者发现源点汇点不连通），然后考虑不在最短路上的所有边，看经过它且从源点走向汇点的最短距离是多少，或者判断是否不存在这样的边。
在具体实现中，求经过u-v这条边的最短距离时，我们直接用min(S-u + u-v + v-T, S-v + v-u + u-T)来求得（S是源点，T是汇点）
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 1e5+10, M = 3e5+10;
int dist1[N],dist2[N],pre[N];
int z[M],x[M],d[M];
typedef pair<int,int> pii;
vector<vector<pii> > adj;
bool st[N];
int main()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>n>>m;
adj.resize(n+1);
for(int i = 1; i <= m; ++i)
{
cin>>z[i]>>x[i]>>d[i];
adj[z[i]].push_back({x[i],d[i]});
adj[x[i]].push_back({z[i],d[i]});
}
memset(dist1,0x3f,sizeof dist1);memset(dist2,0x3f,sizeof dist2);
dist1[1] = 0;
priority_queue<pii,vector<pii>,greater<pii> > q;
set<pii> banned;
q.push({dist1[1],1});
while(q.size())
{
auto [dis,u] = q.top();q.pop();
if(st[u]) continue;
st[u] = true;
for(auto [v,len]:adj[u])
{
if(dist1[v] > dis + len)
{
dist1[v] = dis+len;
pre[v] = u;
q.push({dist1[v],v});
}
}
}
if(dist1[n] == 0x3f3f3f3f)
{
cout<<"-1\n";
return 0;
}
int now = n;
while(1)
{
if(now == 1) break;
banned.insert({pre[now],now});
now = pre[now];
}
dist2[n] = 0;
q.push({0,n});
for(int i = 1; i <= n; ++i) st[i] = 0;
while(q.size())
{
auto [dis,u] = q.top();q.pop();
if(st[u]) continue;
st[u] = true;
for(auto [v,len] : adj[u])
{
if(dist2[v] > dis + len)
{
dist2[v] = dis + len;
q.push({dist2[v],v});
}
}
}
int ans = dist1[n];
int best = 0x3f3f3f3f;
for(int i = 1; i <= m; ++i)
{
int a = z[i],b = x[i];
if(banned.count({a,b}) + banned.count({b,a})) continue;
int mn = dist1[a] + dist2[b] + d[i];
mn = min(mn,dist1[b] + dist2[a] + d[i]);
best = min(mn,best);
}
if(best == 0x3f3f3f3f)
{
cout<<"-1\n";
return 0;
}
cout<<best+ans<<"\n";
return 0;
}
1934D1. XOR Break — Solo Version
题目大意：
定义了一种操作：给定x，选取y(0 < y < x)使得0 < (x \(\oplus\) y) < x，可以将x变成y或者变成x\(\oplus\)y。给定两个数a > b > 0，问能否在63次操作内将a变成b，若可以则给出一个方案，不然输出-1。
细节：
a,b ~ 1e18
思考：
这个63和异或一看就是和二进制表示有关，于是手玩一下，分几个类别分别构造/证明不可能，就可以了。
感觉这个题的思路不是特别难，但要想清楚还是比较麻烦的。下面是具体的思考路径：
- 如果在二进制表示中a \(\supseteq\) b：那么直接变成b，是可以一步到位的（a \(\oplus\) b 肯定大于0，因为a \(\not=\) b; 而且肯定 \(\leq\) a，因为0一定异或成0,1异或成0和1无所谓，而如果a \(\oplus\) b == a，就代表着a == b || b == 0，矛盾，所以严格小于）
- 从高位到低位考虑第一个a[i] == 0 而 b[i] == 1的位置。（这一部分感觉讲不太明白……但如果画画图就会比较清楚了）
- 如果他前面（这里的“前面”代表着更高位）只有一个位置上a[j] == 1，则不可能变成b。反证法：假设可以，那么在某一次操作后，a[j]从1变成了0，要保证操作合法的话肯定会变成一个比b小的数……那就寄了。（说的不是很明白……）
- 如果他前面有至少两个位置上a[j] == 1，那么我们可以通过一次合法的操作先将a变成c使得c \(\supseteq\) b， 然后变成情况1，就一步到位啦！但是这里有个特殊情况，就是c可能会直接和b相等，这样的话就是总共只操作了一次而非两次，需要注意一下。
代码：
#include<bits/stdc++.h>
using namespace std;
int T;
typedef int64_t ll;
ll x1,x2;
int main()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>T;
while(T--)
{
cin>>x1>>x2;
bitset<60> a(x1);
bitset<60> b(x2);
int dif = -1;
for(int i = 59; ~i; --i)
if(a[i] == 0 && b[i] == 1)
{
dif = i;
break;
}
if(dif == -1)
{
cout<<"1\n";
cout<<x1<<' '<<x2<<'\n';
continue;
}
int num = 0;
for(int i = dif+1; i < 60; ++i)
num += a[i];
if(num == 1)
{
cout<<"-1\n";
continue;
}
int spec = -1;
for(int i = dif+1; i < 60; ++i)
if(a[i] == 1 && b[i] == 0)
{
spec = i;
break;
}
assert(spec != -1);
ll nxt = 0;
for(int i = 0; i < 60; ++i)
if(i != spec && (a[i] || b[i]))
nxt |= 1ll<<i;
if(nxt == x2)
{
cout<<"1\n";
cout<<x1<<' '<<x2<<'\n';
continue;
}
cout<<"2\n";
cout<<x1<<' '<<nxt<<' '<<x2<<'\n';
}
return 0;
}
一些实现上的细节：
用bitset转化为二进制表达真的很方便！
F. Turtle Mission: Robot and the Earthquake
题意：
有个 n \(\times\) m 的棋盘（0-based），某些位置有陨石，每过一秒，每个陨石会向上移动一格（碰到顶部就循环）。人一开始在（0,0），可以进行三种移动：向上一格，向右一格，向下一格。碰到陨石就gg，问走到点（n-1,m-1）需要的最短时间是多少，或者根本走不到。
细节：
棋盘是cyclic的，就是说点（n - 1 , i）往下走会到点（0 , i），点（0 , i）往上走会到点（n - 1 , i）。
一开始最右边一列以及初始点（0 , 0）上保证没有陨石。
人向右走不撞到陨石的条件是：（（x + 1）% n,（y + 1）% m）上没有陨石。
向下走不撞到陨石的条件是：（（x + 1）% n, y）和（（x + 2）% n, y）上都没有陨石。
n,m ~ 1000
思路：
毫无思路，这题基本是抄了答案。一开始想了一个做法就是对每个点求出走到这个点的最小时间，然后dp。但很显然不对，因为对于非终点而言，最小时间不一定是最优的。然后就不会做啦！
但答案的方法很巧妙。考虑转换坐标系，以陨石为参考系。这样人的移动就变成了：不动、向右下、向下下。然后对这个参考系下每个点求个距离。然后枚举到最右边一列（i , m-1）时先走到哪个i，更新n次答案即可。（在这个参考系下面每个点的最短时间就是最优的，因为不用考虑会不会被撞死了）
代码：
#include<bits/stdc++.h>
using namespace std;
int T,n,m;
const int N = 1010;
int g[N][N];
int dist[N][N];
typedef pair<int,int> pii;
int main()
{
ios::sync_with_stdio(false),cin.tie(0);
cin>>T;
while(T--)
{
cin>>n>>m;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
cin>>g[i][j],dist[i][j] = -1;
dist[0][0] = 0;
queue<pii> q;
q.push({0,0});
while(q.size())
{
auto [x,y] = q.front();
q.pop();
int x1 = (x+1)%n, y1 = (y+1)%m;
if(g[x1][y1] == 0 && dist[x1][y1] == -1)
{
dist[x1][y1] = dist[x][y] + 1;
q.push({x1,y1});
}
y1 = y;
if(g[x1][y1]) continue;
x1 = (x1+1)%n;
if(g[x1][y1]) continue;
if(dist[x1][y1] == -1)
{
dist[x1][y1] = dist[x][y] + 1;
q.push({x1,y1});
}
}
int ans = 0x3f3f3f3f;
for(int i = 0; i < n; ++i)
{
int t = dist[i][m-1];
if(t == -1) continue;
int pos = (i-t)%n+n;
pos %= n;
ans = min(ans,min(n-1-pos,pos+1)+t);
}
cout<<(ans == 0x3f3f3f3f?-1:ans)<<'\n';
}
return 0;
}
反思：
题解中采用了很漂亮的观察，直接消去了“陨石的运动”这一影响因素，很妙！
标签：1934D1,1942D,int,cin,y1,做题,push,x1,dp From： https://www.cnblogs.com/BladeWaltz/p/18386168