cf1191 解题报告

A-简单模拟

脑内算出来让计算机输出

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
    int x;
    cin>>x;
    if(x%4==0) return puts("1 A"),0;
    if(x%4==1) return puts("0 A"),0;
    if(x%4==2) return puts("1 B"),0;
    if(x%4==3) return puts("2 A"),0;
    return 0;
}

B-细节模拟

脑内算出来让计算机输出。wa了几发、、、

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
string a[4];
int main() {
    cin>>a[1]>>a[2]>>a[3];
    sort(a+1,a+1+3);
    if(a[1]==a[2]&&a[2]==a[3]) return puts("0"),0;
    if(a[1][1]==a[2][1] and a[1][1]==a[3][1]) {
        int x=a[1][0]-'0',y=a[2][0]-'0',z=a[3][0]-'0';
        int b[44];
        b[1]=x,b[2]=y,b[3]=z;
        sort(b+1,b+1+3);
        if(b[1]+1==b[2]&&b[2]+1==b[3]) return puts("0"),0;  
    }
    int x=a[1][0]-'0',y=a[2][0]-'0',z=a[3][0]-'0';
    if(a[1][1]==a[2][1])
        if(abs(x-y)<=2) return puts("1"),0; 
    if(a[1][1]==a[3][1])
        if(abs(x-z)<=2) return puts("1"),0; 
    if(a[2][1]==a[3][1])
        if(abs(y-z)<=2) return puts("1"),0;
    puts("2");
    return 0;
}

C-模拟

每次暴力模拟就行，(a[l]-l+1)%k为当前在块内的初始位置。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;
int n,a[N],m,k;
signed main() {
    cin>>n>>m>>k;
    for(int i=1;i<=m;++i) cin>>a[i];
    sort(a+1,a+1+m);
    int ans=0,l=1;
    while(l<=m) {
        int j=(a[l]-l+1)%k;
        if(!j) j=k;
        while(j+(a[l+1]-a[l])<=k&&l<=m) l++,j+=a[l]-a[l-1];
        l++,ans++;
    }
    cout<<ans;
    return 0;
}

D-博弈

一条线上有n个点，点点之间不能占同一个位置。
先把开始就输的结果判掉。
之后的局面就要是0~n-1的排列了。
博弈是真的不会o(╥﹏╥)o

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+7;
int n,a[N],sum;
signed main() {
    cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i],sum+=a[i];
    sort(a+1,a+1+n);
    int flag=0;
    for(int i=1;i<n;++i)
        if(a[i]==a[i+1])
            if(a[i]==0||(i>1&&a[i-1]+1==a[i])||++flag>1)
                return puts("cslnb"),0;
    int las=sum-n*(n-1)/2;
    if(las&1) puts("sjfnb");
    else puts("cslnb");
    return 0;
}

E-博弈

咕咕咕

F-数据结构

离散化后，枚举a的位置。
然后考虑一行的贡献。
把此行及其以上的点压缩到数轴上。
贡献显然产生在有此行的点的区间内，计算出来区间个数就是此行的贡献。
因为不在此行的话，上面已经统计过了。
具体统计的话，就是总的区间-不包含的小区间。
统计用BIT就OK。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+7;
int n,b[N],lsh[2][N];
struct node {
    int first,second;
    bool operator < (const node &b) const {
        return first==b.first?second<b.second:first>b.first;
    }
}a[N];
namespace BIT {
    int sum[N];
    int lowbit(int x) {return x&-x;}
    void add(int x) {for(int i=x;i<=n;i+=lowbit(i)) sum[i]++;}
    int query(int x) {int ans=0;for(int i=x;i>=1;i-=lowbit(i)) ans+=sum[i];return ans;}
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i) {
        scanf("%d%d",&a[i].second,&a[i].first);
        lsh[0][i]=a[i].first;
        lsh[1][i]=a[i].second;
    }
    sort(lsh[0]+1,lsh[0]+1+n);
    sort(lsh[1]+1,lsh[1]+1+n);
    int len[2];
    len[0]=unique(lsh[0]+1,lsh[0]+1+n)-lsh[0]-1;
    len[1]=unique(lsh[1]+1,lsh[1]+1+n)-lsh[1]-1;
    for(int i=1;i<=n;++i) {
        a[i].first=lower_bound(lsh[0]+1,lsh[0]+1+len[0],a[i].first)-lsh[0];
        a[i].second=lower_bound(lsh[1]+1,lsh[1]+1+len[1],a[i].second)-lsh[1];
    }
    sort(a+1,a+1+n);
    ll ans=0;
    for(int i=len[0],now=0,tmp=0,gs=0;i>=1;--i) {
        int las=0;
        while(a[now+1].first==i&&now+1<=n) {
            now++;
            tmp=BIT::query(a[now].second-1)-BIT::query(las);
            ans-=1LL*tmp*(tmp+1)/2;
            if(!b[a[now].second]) {
                BIT::add(a[now].second);
                b[a[now].second]=1;
                gs++;
            }
            las=a[now].second;
        }
        tmp=gs-BIT::query(las);
        ans-=1LL*tmp*(tmp+1)/2;
        ans+=1LL*gs*(gs+1)/2;
    }
    cout<<ans<<"\n";
    return 0;
}