头像

asdypeij




离线:1天前


最近来访(1)
用户头像
hepanrong.

活动打卡代码 AcWing 2983. 玩具

#include <bits/stdc++.h>
using namespace std;
#define F(i,j,k) for (signed i=signed(j);i<=signed(k);i++)
#define endl '\n'
#define int long long
const int maxn=5005;

#define x1 dxfgbhj
#define x2 rctvybjn
#define y1 rtgbhn
#define y2 hughmjn

int n,m,x1,y1,x2,y2,u,l,x,y;

struct Point{
    int x,y;
    Point(){}
    Point(int _x,int _y){x=_x,y=_y;}
    Point operator -(const Point p)const{
        return Point(x-p.x,y-p.y);
    }
    void print(){
        cerr<<"("<<x<<","<<y<<") ";
    }
}p[maxn][2],toy[maxn];

int tot[maxn];

int cross(Point a,Point b){
    return a.x*b.y-b.x*a.y;
}

bool check(int i){
    Point v1=p[i][1]-p[i][0],v2=Point(x,y)-p[i][0];
    return cross(v2,v1)>0;
}

signed main() { 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int i=0;

    while(cin>>n>>m>>x1>>y1>>x2>>y2&&n){
        if(i) cout<<endl;
        memset(tot,0,sizeof tot);
        F(i,1,n){
            cin>>u>>l;
            p[i][0]={u,y1},p[i][1]={l,y2};
        }
        p[n+1][0]={x2,y1},p[n+1][1]={x2,y2};
        // F(i,1,n+1) p[i][0].print(),p[i][1].print(),cerr<<endl;
        F(i,1,m){
            cin>>x>>y;
            int l=1,r=n+1;
            while(l<r){
                int mid=(l+r)/2;
                if(check(mid)) r=mid;
                else l=mid+1;
            }
            tot[l-1]++;
        }
        F(i,0,n) cout<<i<<": "<<tot[i]<<endl;
        i++;
    }
    return 0; 
}








活动打卡代码 AcWing 2815. 三维偏序

asdypeij
18天前
#include<bits/stdc++.h>
#define F(i,j,k) for(signed i=signed(j);i<=signed(k);i++)
#define endl '\n'
using namespace std;
const int maxn=1e5+5;

int n,m,ans[maxn];

struct Fentree{
    int t[maxn*2];
    void add(int x,int k){for(;x<=m;x+=x&-x) t[x]+=k;}
    int query(int x){
        int ans=0;
        for(;x;x-=x&-x) ans+=t[x];
        return ans;
    } 
}t;

struct Point{
    int a,b,c,cnt=1,ans=0;
    bool operator <(const Point& p)const{
        if(a!=p.a) return a<p.a;
        if(b!=p.b) return b<p.b;
        return c<p.c;
    }
    bool operator ==(const Point& p)const{
        return a==p.a&&b==p.b&&c==p.c;
    }
}a[maxn],tmp[maxn];

void cdq(int l,int r){
    if(l>=r) return;
    int mid=(l+r)/2;
    cdq(l,mid),cdq(mid+1,r);
    int i=l,j=mid+1,k=1;
    while(i<=mid&&j<=r){
        if(a[i].b<=a[j].b) t.add(a[i].c,a[i].cnt),tmp[k++]=a[i++];
        else a[j].ans+=t.query(a[j].c),tmp[k++]=a[j++];
    }
    while(i<=mid) t.add(a[i].c,a[i].cnt),tmp[k++]=a[i++];
    while(j<=r) a[j].ans+=t.query(a[j].c),tmp[k++]=a[j++];
    F(i,l,mid) t.add(a[i].c,-a[i].cnt);
    for(int i=l,j=1;i<=r;i++,j++) a[i]=tmp[j];
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    F(i,1,n) cin>>a[i].a>>a[i].b>>a[i].c;
    sort(a+1,a+1+n);
    int k=2;
    F(i,2,n) {
        if(a[i]==a[k-1]) a[k-1].cnt++;
        else a[k++]=a[i];
    }
    cdq(1,k-1);
    F(i,1,k-1) ans[a[i].ans+a[i].cnt-1]+=a[i].cnt;
    F(i,0,n-1) cout<<ans[i]<<endl;
    return 0;
}



活动打卡代码 AcWing 211. 计算系数

asdypeij
2个月前
// Problem: P1313 [NOIP2011 提高组] 计算系数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1313
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define F(i,j,k) for (signed i=signed(j);i<=signed(k);i++)
#define endl '\n'
#define int long long
const int mod=10007;

int a,b,k,n,m;
int qPow(int a,int b){
    int ans=1;
    while(b){
        if(b%2) (ans*=a)%=mod;
        (a*=a)%=mod,b/=2;
    }
    return ans;
}
int inv(int x){return qPow(x,mod-2);}
int P(int a,int b){//从b个数中选a个数的个数
    int ans=1;
    for(int i=b,j=1;j<=a;i--,j++) (ans*=i)%=mod;
    return ans;
}
int fac(int x){return x==1?1:x*fac(x-1)%mod;}

signed main() { 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>a>>b>>k>>n>>m;
    cout<<qPow(a,n)*qPow(b,m)%mod*P(n,k)%mod*inv(fac(n))%mod<<endl;
    return 0; 
}








活动打卡代码 AcWing 142. 前缀统计

asdypeij
2个月前
// Problem: P8306 【模板】字典树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8306
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define F(i,j,k) for (signed i=signed(j);i<=signed(k);i++)
#define endl '\n'
//#define int long long
int T;
struct trie{
    struct trie_node{
        int cnt=0;
        unordered_map<char,int> c;
    };
    vector<trie_node> a={{}};
    void insert(string s){
        int node=0;
        for(auto i:s) {
            if(a[node].c.count(i)) node=a[node].c[i];
            else a.push_back({}),a[node].c[i]=a.size()-1,
                node=a.size()-1;
        }
        a[node].cnt++;
    }
    int get_node(string s){
        int node=0,ans=0;
        for(auto i:s){
            if(a[node].c.count(i)) node=a[node].c[i],ans+=a[node].cnt;
            else return ans;
        }
        return ans;
    }
};
string rev(string s){
    reverse(begin(s),end(s));
    return s;
}
main() { 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,q;
    string s;
    trie t;
    cin>>n>>q;
    F(i,1,n) cin>>s,t.insert(s);
    F(i,1,q) cin>>s,cout<<t.get_node(s)<<endl;
    return 0; 
}



asdypeij
2个月前

算法

__int128

中间乘法时转化为__int128,最后再以long long输出

时间复杂度

$O(1)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long a,b,p;
    cin>>a>>b>>p;
    cout<<(long long)(__int128(a)*b%p);
    return 0;
}