Comet OJ - Contest #8
传送门
A.杀手皇后
签到。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005;
vector <string> v;
int n;
string s;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> s;
v.push_back(s);
}
sort(v.begin(),v.end());
cout << v[0];
return 0;
}
B.支援城市
把式子拆开就行。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n;
int w[N];
ll sumv,sum;
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> w[i],sum += w[i];
for(int i = 1; i <= n; i++) sumv += 1ll * w[i] * w[i];
for(int i = 1; i <= n; i++) {
ll ans = sumv + 1ll * n * w[i] * w[i];
ans -= 2ll * w[i] * sum;
cout << ans << " n"[i == n];
}
return 0;
}
C.符文能量
手玩一下样例，发现答案与合并顺序无关，然后就可以愉快的(dp)了。
因为最终序列的状态是有三个阶段的，所以就(dp[i,0/1/2])来表示三种状态，然后分别转移就行。
Code
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
ll n,k;
ll a[N],b[N],c[N];
ll dp[N][3][2];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
for(int i = 1; i < n; i++) c[i] = a[i + 1] * b[i];
n--;
for(int i = 1; i <= n; i++) {
dp[i][0][0] = dp[i - 1][0][0] + c[i];
dp[i][0][1] = min(dp[i - 1][0][1],dp[i - 1][1][1]) + c[i];
dp[i][1][0] = dp[i - 1][0][0] + c[i] * k;
dp[i][1][1] = min(dp[i - 1][2][1],dp[i - 1][1][0]) + c[i] * k;
dp[i][2][1] = min(dp[i - 1][2][1],dp[i - 1][1][0]) + c[i] * k * k;
}
ll ans = INF;
ans = min(ans,min(dp[n][0][0],min(dp[n][0][1],min(dp[n][1][0],min(dp[n][1][1],dp[n][2][1])))));
cout << ans;
return 0;
}
还有一种前缀和的搞法，感觉说不太清楚，见代码吧：
Code
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
ll n,c[N],d[N];
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
for(int i = 1; i < n; i++) c[i] = a[i + 1] * b[i],d[i] = d[i - 1] + c[i];
n--;
ll ans = min(d[n],d[n] * k * k),Min = 0;
for(int i = 1; i <= n; i++) {
ans = min(ans,c[i] * k + d[i - 1] * k * k + d[n] - d[i] + Min);
Min = min(Min,-d[i] * k * k + c[i] * k + d[i - 1]);
}
cout << ans;
return 0;
}
D.菜菜种菜
题目给出的询问都为连续的区间，考虑离线处理.
将题目所求转化为数学语言就是，对于一段区间[l,r]，找到所有的点(u)，满足对于所有的((u,v))，不存在(vin [l,r])。
那么我们就可以直接对于所有的点找到一个最大区间[L,R]，表示在这个区间中，点(u)是不能到达任意点的，那么我们对于每个区间([l,r])，其中所有的点(u)对答案有贡献的话就会满足：(Lleq l,rleq R)。
如果是按区间左端点来求(ans)，我们依次枚举，遇到一个(L)就插入点(u)，遇到(R+1)就减去，对于每一个询问区间([l,r])，我们只需(query(r))就行。因为这个时候我们是保证了(Lleq l)的，只要(R>r)就行了。
如果之前是按右端点来搞，在更新的时候就是在点(L)插入，然后在点(u+1)减去了，就不像刚才在点(R+1)时插入一个点。这时我们只用(query(l))就行。
代码如下：
Code
#include <bits/stdc++.h>
#define MP make_pair
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e6 + 5;
int n,m,q;
short a[N];
int l[N],r[N];
vector <pii> v[N];
vector <int> del[N];
int c[N];
int lowbit(int x) {return x & (-x);}
void update(int x,int v) {
for(; x < N; x += lowbit(x)) c[x] += v;
}
ll query(int x) {
ll ans = 0;
for(; x; x -= lowbit(x)) ans += c[x];
return ans;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n >> m >> q;
memset(r,INF,sizeof(r));
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= m; i++) {
int u,v; cin >> u >> v;
if(v < u) l[u] = max(l[u],v);
else r[u] = min(r[u],v);
}
for(int i = 1; i <= n; i++) {
l[i]++;
if(r[i] == INF) continue;
del[r[i]].push_back(i);
}
for(int i = 1; i <= q; i++) {
int L,R; cin >> L >> R;
v[R].push_back(MP(L,i));
}
ll ans = 0;
for(int i = 1; i <= n; i++) {
update(l[i],a[i]);
update(i + 1,-a[i]);
for(auto it : del[i]) {
update(l[it],-a[it]);
update(it + 1,a[it]);
}
for(auto it : v[i]) {
ans ^= 1ll * it.second * query(it.first);
}
}
cout << ans;
return 0;
}
