只做了几个题。
B. A Plus B Problem：
一开始做的时候思路有点乱，后面理清楚了，就是说不用10进制来维护，用没有进位之后的数来维护，这样每次操作之后就是加1减1的操作了。
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double ld;
typedef pair<int,int> pii;
const int N = 2e6 + 5;
const int M = 1e6 + 5;
const LL Mod = 998244353;
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
inline long long ADD(long long x,long long y) {
if(x + y < 0) return ((x + y) % Mod + Mod) % Mod;
return (x + y) % Mod;
}
inline long long MUL(long long x,long long y) {
if(x * y < 0) return ((x * y) % Mod + Mod) % Mod;
return x * y % Mod;
}
inline long long DEC(long long x,long long y) {
if(x - y < 0) return (x - y + Mod) % Mod;
return (x - y) % Mod;
}
int a[5][N],cd[N];
struct Node{int L,r,mi,mx,tag;}node[N << 2];
void Pushup(int idx) {
node[idx].mx = max(node[idx << 1].mx,node[idx << 1 | 1].mx);
node[idx].mi = min(node[idx << 1].mi,node[idx << 1 | 1].mi);
}
void Pushdown(int idx) {
if(node[idx].tag != 0) {
int tag = node[idx].tag;
node[idx << 1].mx += tag,node[idx << 1].mi += tag,node[idx << 1].tag += tag;
node[idx << 1 | 1].mx += tag,node[idx << 1 | 1].mi += tag,node[idx << 1 | 1].tag += tag;
node[idx].tag = 0;
}
}
void build(int L,int r,int idx) {
node[idx].L = L,node[idx].r = r,node[idx].tag = 0;
if(L == r) {
node[idx].mi = node[idx].mx = cd[L];
return ;
}
int mid = (L + r) >> 1;
build(L,mid,idx << 1);
build(mid + 1,r,idx << 1 | 1);
Pushup(idx);
}
void update(int L,int r,int val,int idx) {
if(node[idx].L > node[idx].r || L > r) return ;
if(node[idx].L >= L && node[idx].r <= r) {
node[idx].mi += val;
node[idx].mx += val;
node[idx].tag += val;
return ;
}
Pushdown(idx);
int mid = (node[idx].L + node[idx].r) >> 1;
if(mid >= L) update(L,r,val,idx << 1);
if(mid < r) update(L,r,val,idx << 1 | 1);
Pushup(idx);
}
void update2(int x,int val,int idx) {
if(node[idx].L == node[idx].r) {
node[idx].mi = node[idx].mx = val;
return ;
}
Pushdown(idx);
int mid = (node[idx].L + node[idx].r) >> 1;
if(mid >= x) update2(x,val,idx << 1);
else update2(x,val,idx << 1 | 1);
Pushup(idx);
}
int query(int x,int idx) {
if(node[idx].L == node[idx].r) return node[idx].mi;
Pushdown(idx);
int mid = (node[idx].L + node[idx].r) >> 1;
if(mid >= x) return query(x,idx << 1);
else return query(x,idx << 1 | 1);
}
int query_pos(int L,int r,int id,int idx) {//id = 1 ！= 10,id = 2,!= 9
if(L > r) return -1;
if(node[idx].L == node[idx].r) return node[idx].L;
Pushdown(idx);
int mid = (node[idx].L + node[idx].r) >> 1,val = 9;
if(id == 1) val = 10;
if(mid < r && (node[idx << 1 | 1].mx != val || node[idx << 1 | 1].mi != val)) {
int ans = query_pos(L,r,id,idx << 1 | 1);
if(ans != -1) return ans;
else if(mid >= L && (node[idx << 1].mx != val || node[idx << 1].mi != val)) return query_pos(L,r,id,idx << 1);
return -1;
}
else if(mid >= L && (node[idx << 1].mx != val || node[idx << 1].mi != val)) return query_pos(L,r,id,idx << 1);
return -1;
}
void solve() {
int n,q;scanf("%d %d",&n,&q);
string s;cin >> s;
for(int i = 1;i <= n;++i) a[1][i] = s[i - 1] - '0';
cin >> s;
for(int i = 1;i <= n;++i) a[2][i] = s[i - 1] - '0';
int t = 0;
for(int i = n;i >= 1;--i) {
int f = (a[1][i] + a[2][i] + t) / 10;
cd[i] = a[1][i] + a[2][i] + t;
t = f;
}
build(1,n,1);
while(q--) {
int r,c,d;scanf("%d %d %d",&r,&c,&d);
int ch = 0,id;
if(r == 1) id = 1;
else id = 2;
if(a[id][c] != d) ch++;
int dis = a[id][c] - d;
a[id][c] = d;
int tmp = query(c,1);
int ed = tmp - dis;
if(tmp != ed) ch++;
update2(c,ed,1);
if(ed < 10 && tmp >= 10){
int pos = query_pos(1,c - 1,1,1);
if(pos == -1) pos = 1,ch += c - 1;
else ch += c - pos;
update(pos,c - 1,-1,1);
}
else if(ed >= 10 && tmp < 10) {
int pos = query_pos(1,c - 1,2,1);
if(pos == -1) pos = 1,ch += c - 1;
else ch += c - pos;
update(pos,c - 1,1,1);
}
printf("%d %d\n",ed % 10,ch);
}
}
int main() {
// int ca;scanf("%d",&ca);
// while(ca--) {
solve();
//}
//system("pause");
return 0;
}
/*
5 5
05617
14382
1 3 2
2 5 4
5 5
26321
47764
2 5 9
2 4 7
1 4 2
1 3 2
1 4 3
5 5
99990
00000
2 4 1
2 5 1
2 5 1
*/
View Code
这题相对要简单一些，只要能想到了，主要是判断能不能买到环的情况，如果能买到一个，和买到多个一样都是2轮。也就是说找到一个环的权值最小。
dij找一下最小权值环就行了。
D：Assumption is All You Need 银牌题？
这感觉也就是个2000多分左右的构造，不是很难，大概半小时推出了解法。
考虑对于一个小的数，一次逆序对操作之后，它只会向前走。
我们拟定现在比它小的数都无法动了。那么如果目标位置在它后面，那么如果不靠比它小的肯定无解。
现在我们去动比它小的，很显然，这个移动规律有传递性，如果我们利用比它小的完成了，那么比它小的肯定在更前面了。
所以我们考虑从小到大去对位，那么对于当前i，如果需要借用小的，那么肯定无解。
经过上面操作很显然，我们每次去动都是向左移动，那么每次对位我们都去找一个可动区间里的最小的替换它是最优的。
最优的这个很容易证明，因为比他大的都可以移动到这个位置，所以找最小的。
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double ld;
typedef pair<int,int> pii;
const int N = 2e6 + 5;
const int M = 1e6 + 5;
const LL Mod = 998244353;
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
inline long long ADD(long long x,long long y) {
if(x + y < 0) return ((x + y) % Mod + Mod) % Mod;
return (x + y) % Mod;
}
inline long long MUL(long long x,long long y) {
if(x * y < 0) return ((x * y) % Mod + Mod) % Mod;
return x * y % Mod;
}
inline long long DEC(long long x,long long y) {
if(x - y < 0) return (x - y + Mod) % Mod;
return (x - y) % Mod;
}
int a[2025],b[2025],pos1[2025],pos2[2025];
vector<pii> ans;
int Find(int L,int r,int k) {
int mi = INF;
for(int i = L;i <= r;++i) {
if(a[i] > k && a[i] < mi) mi = a[i];
}
return mi;
}
void change(int x,int y) {
int xx = pos1[x],yy = pos1[y];
pos1[y] = xx,pos1[x] = yy;
swap(a[xx],a[yy]);
ans.push_back(pii{min(xx,yy),max(xx,yy)});
}
void solve() {
ans.clear();
int n;scanf("%d",&n);
for(int i = 1;i <= n;++i) scanf("%d",&a[i]),pos1[a[i]] = i;
for(int i = 1;i <= n;++i) scanf("%d",&b[i]),pos2[b[i]] = i;
bool flag = 0;
for(int i = 1;i <= n;++i) {
if(pos2[i] > pos1[i]) {flag = 1;break;}
while(1) {
int tmp = Find(pos2[i],pos1[i] - 1,i);
if(tmp == INF) break;
change(i,tmp);
}
if(pos1[i] != pos2[i]) change(i,a[pos2[i]]);
}
if(flag) printf("-1\n");
else {
printf("%d\n",ans.size());
for(auto v : ans) printf("%d %d\n",v.first,v.second);
}
}
int main() {
int ca;scanf("%d",&ca);
while(ca--) {
solve();
}
//system("pause");
return 0;
}
View Code