SDNU 1st

A
题意大概是找到两个和为n的数字a 和 b，使得a/b是最简真分数（a < b）
暴力查找(n<1000)

#include<bits/stdc++.h>
using namespace std;

int n;

int gcd(int x,int y) {
    if(y == 0) return x;
    return gcd(y,x % y);
}

int main() {
    scanf("%d",&n);
    for(int i = n / 2;i >= 1; --i) {
        int y = n - i;
        if(gcd(i,y) == 1) {
            printf("%d %d\n",i,y);
            return 0;
        }
    }
    return 0;
}

B
题意：n个房子，其中有k个房子里有人，这k个房子的编号未知，现在小M要买所有附近(编号相差1)有人住的空房子，问最多和最少买多少个房子
n == k 或者 k == 0 时只能买0个
除此之外，最少能买的一定是1个（k个有人的房子编号从1--k挨着，只能买编号为k+1的房子
最多   如果n >= 3*k,  那么最好是 2，5，8，这样，最多买2*k个
n < 3 *k,能买n-k个，列式子计算

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n,k,m;

int main() {
    scanf("%lld%lld",&n,&k);
    if(n == k || k == 0) printf("0 0\n");
        else {
            if(n <= 3 * k) m = n - k;
                else m = 2 * k;
            printf("1 %lld\n",m);
        }
    return 0;
}

C
原本有一个航班表，因为一些原因要推迟航班出行k小时，现在要安排新的航班表，要求新的时间不能比原来的时间，给出几个航班延迟一小时的花费，问怎么安排能使花费最少，给出最少话费和每个飞机的出发时间。
贪心：总花费=Σciti - Σici   后面部分固定，求最小的citi 且 ti>=i
优先队列

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 4e5 + 10;
struct node{
    ll x,id;
    bool friend operator<(const node &x,const node &y){
        return x.x < y.x;
    }
};

ll a[maxn],k,n,b[maxn],ans;
priority_queue<node>q;

int main(){
    scanf("%lld%lld",&n,&k);
    for(int i = 1;i <= n; ++i){
        scanf("%lld",&a[i]);
        ans -= a[i] * i;
    }
    while(!q.empty()) q.pop();
    for(int i = 1;i <= k; ++i){
        node p;
        p.x = a[i];
        p.id = i;
        q.push(p);
    }
    int tot = k + 1;
    while(!q.empty()){
        if(tot <= n){
            node p;
            p.x = a[tot];
            p.id = tot;
            q.push(p);
        }
        node p = q.top();
        q.pop();
        b[p.id] = tot;
        ans += tot * p.x;
        tot++;
    }
    printf("%lld\n",ans);
    for(int i = 1;i < n; ++i){
        printf("%lld ",b[i]);
    }
    printf("%lld\n",b[n]);
    return 0;
}

F
俩人轮流分数字，先将所有的数字分成1为赢，玩家1赢输出1，否则输出2，每次都是玩家1先分
谁先分2的倍数就肯定能赢
堆依次增加的，所以当玩家1赢得本轮比赛后，下一堆数字来临时，应该是玩家2是先手，依次循环标记本轮几号玩家赢，然后判断满足条件即可
 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 1e5 + 10;
ll a[maxn],sum,n;

int main(){
    scanf("%lld",&n);
    sum = 0;
    for(int i = 0;i < n; ++i) scanf("%lld",&a[i]);
    for(int i = 0;i < n; ++i){
        sum += a[i] - 1;
        if(sum % 2) printf("1\n");
            else printf("2\n");
        sum %= 2;
    }
    return 0;
}

J题
二维前缀和裸
 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e7 + 10;
int n,m,k,p,q,T,x,y,xx,yy;
int a[maxn];

int getid(int i,int j)
{
    if(!i || !j || i > n || j > m) return 0;
    return (i - 1) * m + j;
}

void add(int i,int j,int v)
{
    if(!getid(i,j)) return;
    a[getid(i,j)] += v;
}

void getsum()
{
    for(int i = 1;i <= n; ++i)
            for(int j = 1;j <= m; ++j)
                a[getid(i,j)] += a[getid(i - 1,j)] +
                                 a[getid(i,j - 1)] - a[getid(i - 1,j - 1)];
}

int main()
{
    while(~scanf("%d%d",&n,&m)){
        for(int i = 1;i <= n; ++i)
            for(int j = 1;j <= m; ++j)
                a[getid(i,j)]=0;
        scanf("%d",&p);
        while(p--)
        {
            scanf("%d%d%d%d",&x,&y,&xx,&yy);
            add(x,y,1);
            add(xx + 1,yy + 1,1);
            add(xx + 1,y,-1);
            add(x,yy + 1,-1);
        }
        getsum();
        for(int i = 1;i <= n; ++i)
            for(int j = 1;j <= m; ++j)
                a[getid(i,j)] = a[getid(i,j)] > 0 ? 1 : 0;
        getsum();
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d%d%d%d",&x,&y,&xx,&yy);
            int ans = a[getid(xx,yy)] + a[getid(x - 1,y - 1)] -
                      a[getid(x - 1,yy)] - a[getid(xx,y - 1)];
            if(ans == (xx - x + 1) * (yy - y + 1)) puts("YES");
                else puts("NO");
        }
    }
    return 0;
}