比赛链接：http://codeforces.com/contest/854
A. Fraction
解法：按照题意模拟即可。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
for(int i=n/2; i>=1; i--){
if(__gcd(i, n-i) == 1){
printf("%d %d\n", i,n-i);
return 0;
}
}
return 0;
}B. Maxim Buys an Apartment
题意：有n个屋子，其中k个屋子是有人住的，如果第i个屋子有人住，那么第i-1个屋子和第i+1个屋子就是特殊的，方便起见这里我们将特殊屋子的数量记为ans。然后给你n和k，让你输出最小的ans和最大的ans。
解法：如果k和n一样多或者是k为0显然输出0 0，然后就是贪心了，除去特殊情况后，最小全都是1，那么剩下的就是最大值了，当k≤n3时，最大值就是k×2，当k>n3时，最大值就是n−k，化简一下发现可以直接取min(n−k,k×2)。
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k, mx, mi;
cin >> n >> k;
if(k == 0 || k == n){
printf("0 0\n");
return 0;
}
else{
mi = 1;
mx = min(n-k, k*2);
}
cout << mi << " " << mx << endl;
return 0;
}题意：n个人 分成两派, 问最后那一派获得胜利, 规则是这样的, 首先从1遍历到n 如果出现D, 那么他可以什么都不做, 也可以让某一个R退出比赛, 一轮过后假设还剩k个人 , 继续从1遍历到k.
解法:很显然要采取贪心的策略, 如果是D那么他肯定会使他右边离他最近的R推出比赛, 这样才能达到最策略, 右边没有了 则从最左边开始取.直接模拟了
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
priority_queue <pair<int, int> > q;
int res[300005];
int main()
{
int n, k;
cin >> n >> k;
for(int i=1; i<=k; i++){
int x;
scanf("%d", &x);
q.push(make_pair(x, i));
}
LL ans = 0;
for(int i=k+1; i<=n+k; i++){
if(i<=n){
int x;
scanf("%d", &x);
q.push(make_pair(x,i));
}
pair <int,int> a = q.top();
q.pop();
ans += 1LL*(i-a.second)*a.first;
res[a.second] = i;
}
cout << ans << endl;
for(int i=1; i<=n; i++) cout << res[i] << " ";
cout << endl;
return 0;
}题意：有n个地点,m次航班，每次航班有4个信息，起飞日期di、出发地fi、目的地ti、花费ci，起飞和出发地至少有一个是地点0。现在n个地点，每个地点有一个人，他们要到地点0，当所有人都到达的时候，一起待k天，然后再分别回到n个地点。问说最小的花费是多少，如果达不到这个要求输出-1。
解法：我们可以使用 dp 两个方向进行dp1[i] 表示当 i 时间是从 所有点出发到 0 点的最小花费 ,dp2[i] 表示 i 时间时从 0点到 所有点 的花费最小值 这样我们就可以dp了 然后就是如果不能到 所有点我们就不更新如果可以到所有点我们就进行更新dp的最小值 过程中保留一个 sum 记录最小花费即可。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+7;
struct node{
int from, to, cost;
node(){}
node(int from, int to, int cost):from(from),to(to),cost(cost){}
};
vector <node> v[maxn];
int n, m, k;
LL dp1[maxn], dp2[maxn];//dp1[i]表示当i时间是从所有点出发到0的最小花费,dp2[i]表示当i时间是从0出发到所有点的最小花费
LL mi1[maxn], mi2[maxn];
bool vis[maxn];
LL min(LL x, LL y){
if(x == -1) return y;
if(y == -1) return x;
if(x > y) return y;
else return x;
}
int main()
{
scanf("%d %d %d", &n,&m,&k);
memset(dp1, -1, sizeof(dp1));
memset(dp2, -1, sizeof(dp2));
for(int i=0; i<m; i++){
int t, x, y, z;
scanf("%d %d %d %d", &t,&x,&y,&z);
v[t].push_back(node(x,y,z));
}
memset(vis, 0, sizeof(vis));
LL sum = 0;
int cnt = 0;
for(int i=1; i<maxn; i++){
for(int j=0; j<v[i].size(); j++){
node x = v[i][j];
if(x.from){
if(!vis[x.from]){
vis[x.from] = 1;
mi1[x.from] = x.cost;
cnt++;
sum += x.cost;
}
else{
if(mi1[x.from] > x.cost){
sum -= mi1[x.from];
mi1[x.from] = x.cost;
sum += x.cost;
}
}
}
}
if(cnt == n) dp1[i] = min(dp1[i], sum);
}
//
memset(vis, 0, sizeof(vis));
sum = 0;
cnt = 0;
for(int i=maxn-1; i>0; i--){
for(int j=0; j<v[i].size(); j++){
node x = v[i][j];
if(x.to){
if(!vis[x.to]){
vis[x.to] = 1;
mi2[x.to] = x.cost;
cnt++;
sum += x.cost;
}
else{
if(mi2[x.to] > x.cost){
sum -= mi2[x.to];
mi2[x.to] = x.cost;
sum += x.cost;
}
}
}
}
if(cnt == n){
dp2[i] = min(dp2[i], sum);
}
}
//
LL ans = -1;
for(int i=1; i<maxn; i++){
int j = i+k+1;
if(j >= maxn) continue;
if(dp1[i]!=-1 && dp2[j]!=-1){
ans = min(ans, dp1[i]+dp2[j]);
}
}
printf("%lld\n", ans);
return 0;
}解法：查二维平面里有多少点，按行维护主席树，然后每次查一个区间，做差就可以求出二维平面里的点了，然后剩下的容斥一哈就行了，具体是把周围一圈剪掉，然后把四个角加上就好了，这就是个简单容斥。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
const int maxm = maxn*40;
typedef long long LL;
int n, q, tot, a[maxn];
int T[maxn], lson[maxm], rson[maxm], c[maxm];
int build(int l, int r){
int root = tot++;
c[root] = 0;
if(l != r){
int mid=(l+r)/2;
lson[root] = build(l, mid);
rson[root] = build(mid+1, r);
}
return root;
}
int update(int root, int pos, int val){
int newroot = tot++, tmp = newroot;
c[newroot] = c[root]+val;
int l=1, r=n;
while(l<r){
int mid=(l+r)/2;
if(pos<=mid){
lson[newroot] = tot++;
rson[newroot] = rson[root];
newroot = lson[newroot];
root = lson[root];
r = mid;
}
else{
rson[newroot]= tot++;
lson[newroot] = lson[root];
newroot = rson[newroot];
root = rson[root];
l = mid+1;
}
c[newroot] = c[root]+val;
}
return tmp;
}
int query(int root, int L, int R, int l, int r){
if(L > R) return 0;
if(L <= l && r <= R) return c[root];
int mid = (l+r)/2;
int ret = 0;
if(L <= mid) ret += query(lson[root], L, R, l, mid);
if(mid < R) ret += query(rson[root], L, R, mid+1, r);
return ret;
}
int query2(int l, int r, int L, int R){
if(l>r) return 0;
return query(T[r],L,R,1,n)-query(T[l-1],L,R,1,n);
}
LL cal(LL x){
return x*(x-1)/2;
}
int main()
{
tot = 0;
scanf("%d %d", &n,&q);
T[0] = build(1, n);
for(int i=1; i<=n; i++){
scanf("%d", &a[i]);
T[i] = update(T[i-1], a[i], 1);
}
while(q--){
int l, r, d, u;
LL cnt = 0, ans = 0;
scanf("%d %d %d %d", &l,&r,&d,&u);
cnt = query2(1, l-1, 1, n);
ans -= cal(cnt);
cnt = query2(d+1, n, 1, n);
ans -= cal(cnt);
cnt = query2(1, n, 1, r-1);
ans -= cal(cnt);
cnt = query2(1, n, u+1, n);
ans -= cal(cnt);
cnt = query2(1, l-1, 1, r-1);
ans += cal(cnt);
cnt = query2(1, l-1, u+1, n);
ans += cal(cnt);
cnt = query2(d+1, n, 1, r-1);
ans += cal(cnt);
cnt = query2(d+1, n, u+1, n);
ans += cal(cnt);
cnt = cal(n);
ans += cnt;
printf("%lld\n", ans);
}
return 0;
}
京公网安备 11010502036488号