2021“MINIEYE杯”中国大学生算法设计超级联赛（3）

Segment Tree with Pruning

#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<vector>

#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int inf=0x3f3f3f3f;
const double eps=1e-8;

int T;
ll n,k;
map<ll,ll> mp;

ll build(ll n){
    if(mp.find(n)!=mp.end())    return mp[n];
    if(n<=k)    return mp[n]=1;
    return mp[n]=build(n/2)+build(n-n/2)+1;
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin>>T;
    while(T--){
        mp.clear();
        cin>>n>>k;
        cout<<build(n)<<endl;
    }
}

Game on Plane

#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<vector>

#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int inf=0x3f3f3f3f;
const double eps=1e-8;

const int N=100010;

int T;
int n;

map<double,int> mp;
int xa,ya,xb,yb;
int cnt[N],ans[N];
bool vis[N];
int mx,idx;

int main(){
    scanf("%d",&T);
    while(T--){
        mp.clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            cnt[i]=0;
            vis[i]=false;
        }
        mx=0;idx=0;
        for(int i=1;i<=n;i++){
            scanf("%d%d%d%d",&xa,&ya,&xb,&yb);
            int tmp1=yb-ya;
            int tmp2=xb-xa;
//            cout<<(double)tmp1/tmp2<<endl;
            double tmp;
            if(tmp2!=0)    tmp=(double)tmp1/tmp2;
            else    tmp=3e9;
            mp[tmp]++;
            cnt[mp[tmp]]++;
            mx=max(mx,mp[tmp]);
        }
//        cout<<"MX--"<<mx<<endl;
//        for(int i=1;i<=2;i++)
//            printf("%d ",cnt[i]);
//        puts("");
        for(int i=1;i<=mx;i++)    cnt[i]+=cnt[i-1];
//        for(int i=1;i<=mx;i++)    printf("%d ",cnt[i]);
//        puts("");
        for(int i=1;i<mx;i++){
            ans[cnt[i]+1]=cnt[i]-i;
            vis[cnt[i]+1]=true; 
        }
        ans[1]=0;
        for(int i=2;i<=n;i++)
            if(!vis[i])    ans[i]=++idx;
        for(int i=1;i<=n;i++)    printf("%d\n",ans[i]);
    }
}