ARC120 题解A-E及总结
A.Max Add
题意
对于序列((a_1,a_2...a_n))
操作1,2,3...k 将当前序列的最大值加入(a_i),定义(f(i))为第(i)次操作后的序列和
求每个(f(i))
分析
注意到每次加入一个数以后这个数就会成为最大值，于是每次更新即可
代码
花了13分钟AC，感觉手速和推导速度都偏慢一点
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define eps 1e-9
#define db long double
#define equals(a,b) fabs(a-b) < eps
using namespace std;
typedef long long ll;
inline ll rd(){
ll x;
scanf("%lld",&x);
return x;
}
int main(){
int n = rd();
vector<ll> mx(n + 1),v(n + 1),sum(n + 1);
vector<ll> ans(n + 2);
for(int i = 1;i <= n;i++)
v[i] = rd(),mx[i] = max(mx[i - 1],v[i]),sum[i] = sum[i - 1] + v[i];
for(int i = 1;i <= n;i++){
printf("%lld
",sum[i] + i * mx[i] + ans[i]);
ans[i + 1] = ans[i] + sum[i];
}
}
B.Uniformly Distributed
题意
给定(H imes W)的矩形，每个格子可能涂红、蓝、没涂。，从左上角到右下角，每次可以向右或者向下移动一格，要求路线中红蓝颜色相同。问对没涂的染色方案。
分析
不难意识到这是一个很强的条件，稍加分析就知道必须要对角线颜色一样。那么只需要遍历每一条对角线即可，我用的是while循环每次让x--，y++，对角线的条数应该是(H+W-1)
代码
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define eps 1e-9
#define db long double
#define equals(a,b) fabs(a-b) < eps
using namespace std;
typedef long long ll;
inline ll rd(){
ll x;
scanf("%lld",&x);
return x;
}
char s[505][505];
const ll MOD = 998244353;
inline ll ksm(ll a,ll b,ll m = MOD){
ll ans = 1;
ll base = a;
while(b){
if(b & 1) ans *= base,ans %= MOD;
base *= base;
base %= MOD;
b >>= 1;
}
return ans;
}
int main(){
int H = rd();
int W = rd();
for(int i = 1;i <= H;i++)
scanf("%s",s[i] + 1);
int t = H + W - 1;
int ans = 1;
for(int i = 1;i <= t;i++){
int posx = min(i,W);
int posy = 1 + (i > W ? i - W : 0);
int cnt = 0;
int cnt1 = 0,cnt2 = 0;//1 == red 2 == blue
while(posx >= 1 && posy <= H) {
if(s[posy][posx] == '.') cnt++;
else if(s[posy][posx] == 'R') cnt1++;
else cnt2++;
posx--;
posy++;
}
if(cnt1 && cnt2) {
ans = 0;
break;
}
//cerr << cnt1 << ' ' << cnt2 << '
';
if(!cnt1 && !cnt2) ans *= 2,ans %= MOD;
}
cout << ans << '
';
}
C.Swaps2 转化
题意
给定数组(A,B) 寻找最少的操作次数让(A = B)
每次操作选择(i,j)：
1.交换(a_i,a_{i+1})
2.(a_i += 1)
3.(a_{i+1} -=1)
分析
先找性质，把相邻两数交换相当于交换到前面的数要+1,到后面的数要-1。归结为性质就是(a_i + i)总是定值
那么最后匹配到的位置一定有对应的(b_i + i = a'_i = a_j + j)
即把(A)数组转化为(A_i = a_i + i),(B)中会对应到转化后的(A)
如(A:3 1 4) $B: 6 2 0 $
转化后(A:4 3 7),(B:7 4 3)
那么匹配位置应该是(3 1 2)
先在要得到(1 2 3)
不难发现其实就是此时(A)的逆序对数，那么跑一遍树状数组也就解决了
代码
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define eps 1e-9
#define db long double
#define equals(a,b) fabs(a-b) < eps
using namespace std;
typedef long long ll;
inline ll rd(){
ll x;
scanf("%lld",&x);
return x;
}
const int maxn = 2e5 + 5;
struct BIT{
int n;
vector<int> v;
BIT(int n):n(n),v(n + 1){}
void add(int pos,int w){
for(;pos <= n;pos += pos & -pos)
v[pos] += w;
}
ll query(int pos){
ll ans = 0;
for(;pos;pos -= pos & -pos)
ans += v[pos];
return ans;
}
};
int main(){
int n = rd();
vector<int> a(n),b(n),c(n);
map<ll,queue<int>> mp;
ll tot = 0;
for(int i = 0;i < n;i++)
a[i] = rd(),a[i] = i + a[i],mp[a[i]].push(i),tot += a[i];
for(int i = 0;i < n;i++)
b[i] = rd(),b[i] = i + b[i],tot -= b[i];
if(tot) {
puts("-1");
return 0;
}
for(int i = 0;i < n;i++){
c[i] = mp[b[i]].front();
mp[b[i]].pop();
cerr << c[i] << '
';
}
BIT bit(n);
ll ans = 0;
for(int i = 0;i < n;i++)
ans += c[i] - bit.query(c[i] + 1),bit.add(c[i] + 1,1),cerr << ans << '
';
cout << ans << '
';
}
D.Bracket Score 2 巧妙贪心
题意
给定长度(2n)权值数组(A)，求一个括号匹配，使得匹配的括号对贡献和最大，一对括号的贡献计为(|a_i-a_j|)
分析
对数组排序，我们希望总是左边的(n)个数和右边的(n)个数匹配，这样总是可以拉大差值。而稍加思考发现这样总是可以构造的，只需标记前半数组，对该序列做括号匹配即可。
代码
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define eps 1e-9
#define db long double
#define equals(a,b) fabs(a-b) < eps
using namespace std;
typedef long long ll;
const int MOD = 1004535809;
inline int rd(){
int x = 0;
char ch = getchar();
while(ch < '0' || ch > '9'){
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = (ll)x * 10 % MOD + ch - '0';
if(x >= MOD ) x -= MOD;
ch = getchar();
}
return x;
}
int main(){
int n = rd();
vector<pii>v(2 * n);
vector<int>ans(2 * n);
for(int i = 0;i < 2 * n;i++)
v[i].fi = rd(),v[i].se = i;
sort(v.begin(),v.end());
vector<int> pos(2 * n);
for(int i = 0;i < n;i++)
pos[v[i].se] = 1;
int cnt = 0;
int now = 0;
for(int i = 0;i < 2 * n;i++){
if(!cnt) now = pos[i],cnt = 1;
else if(pos[i] == now) cnt++;
else ans[i] = 1,cnt--;
}
for(int i = 0;i < 2 * n;i++)
if(ans[i]) putchar(')');
else putchar('(');
}
E.1D Party 神仙DP + 贪心
题意
有(n)个点表示(n)个人的位置，要求每个人和相邻两人相遇，每次每个人可以选择向左或者向右，每秒移动一个距离
问最短时间
分析
容易想到每个人一定先选择一个方向，碰都每个人以后一直往另一个方向。且连续三个人的初始方向不会相同，(其中两人不相同一定不会更差)
那么(dp_i)表示前(i)个人走完的最短时间的两倍那么转移时枚举第(i-2)个人的初始方向
画画图有
[dp_i = min(max(dp_{i-2},a_i - a_{i-3}),max(dp_{i-3},a_i-a_{i-4}))
]
代码
注意初始化边界
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define eps 1e-9
#define db long double
#define equals(a,b) fabs(a-b) < eps
using namespace std;
typedef long long ll;
const int MOD = 1004535809;
inline int rd(){
int x = 0;
char ch = getchar();
while(ch < '0' || ch > '9'){
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = x * 10 + ch - '0';
ch = getchar();
}
return x;
}
int main(){
int n = rd();
vector<int> dp(n + 2);
vector<int> v(n + 2);
for(int i = 1;i <= n;i++)
v[i] = rd();
dp[1] = 0,dp[2] = v[2] - v[1],v[n + 1] = v[n],v[0] = v[1];
for(int i = 3;i <= n + 1;i++)
dp[i] = min(max(dp[i - 2],v[i] - v[i - 3]),max(dp[i - 3],v[i] - v[i - 4]));
cout << dp[n + 1] / 2;
}