头像

N00Borz




离线:3天前


最近来访(4)
用户头像
凉宫
用户头像
euuuammxzm
用户头像
赤旗
用户头像
Ming_04

活动打卡代码 AcWing 1401. 围住奶牛

N00Borz
3天前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;
const int N=1e4+10;
int n,top;
int stk[N],vis[N];
struct Point{
    double x,y;
    bool operator<(const Point &o){
        return x<o.x||(x==o.x&&y<o.y);
    }
    Point operator-(const Point &o){
        return {x-o.x,y-o.y};
    }
}a[N];
double dot(Point a,Point b)
{
    return a.x*b.x+a.y*b.y;
}
double cross(Point a,Point b)
{
    return a.x*b.y-a.y*b.x;
}
double dist(Point a,Point b)
{
    return sqrt(dot(a-b,a-b));
}
double area(Point a,Point b,Point c)
{
    return cross(b-a,c-a);
}
double andrew()
{
    sort(a,a+n);
    for(int i=0;i<n;++i)
    {
        while(top>=2&&area(a[stk[top-1]],a[stk[top]],a[i])>0)
            vis[stk[top--]]=0;
        stk[++top]=i;
        vis[i]=1;
    }
    vis[0]=false;
    for(int i=n-1;i>=0;--i)
    {
        if(vis[i]) continue;
        while(top>=2&&area(a[stk[top-1]],a[stk[top]],a[i])>0)
            --top;
        stk[++top]=i;
    }
    double res=0;
    for(int i=2;i<=top;++i)
        res+=dist(a[stk[i]],a[stk[i-1]]);
    return res;
}
int main(void)
{
    // sync;
    cin>>n;
    for(int i=0;i<n;++i)
        cin>>a[i].x>>a[i].y;
    printf("%.2lf",andrew());
    return 0;
}
//考虑边界!!!
//Think TWICE, Code ONCE!


活动打卡代码 AcWing 3124. BSGS

N00Borz
2个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<unordered_map>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;
int a,b,p;
int bsgs(int a,int b,int p)
{
    if(1%p==b%p) return 0;
    int k=sqrt(p)+1;
    unordered_map<int,int>hs;
    for(int i=0,j=b%p;i<k;++i)
    {
        hs[j]=i;
        j=1ll*j*a%p;
    }
    int ak=1;
    for(int i=0;i<k;++i) ak=1ll*ak*a%p;
    for(int i=1,j=ak;i<=k;++i)
    {
        if(hs.count(j)) return 1ll*i*k-hs[j];
        j=1ll*j*ak%p;
    }
    return -1;
}
int main(void)
{
    sync;
    while(cin>>a>>p>>b,a||p||b)
    {
        int res=bsgs(a,b,p);
        if(res==-1) cout<<"No Solution"<<endl;
        else cout<<res<<endl;
    }
    return 0;
}
//考虑边界!!!
//Think TWICE, Code ONCE!


活动打卡代码 AcWing 90. 64位整数乘法

N00Borz
2个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;
ll mul(ll a,ll b,ll p)
{
    ll res=0;
    while(b)
    {
        if(b&1) res=(res+a)%p;
        a=a*2%p;
        b>>=1;
    }
    return res;
}
int main(void)
{
    sync;
    ll a,b,p;
    cin>>a>>b>>p;
    cout<<mul(a,b,p)<<endl;
    return 0;
}
//考虑边界!!!
//Think TWICE, Code ONCE!


活动打卡代码 AcWing 219. 剪纸游戏

N00Borz
2个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<unordered_set>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;
const int N=210;
int n,m;
int f[N][N];
int sg(int x,int y)
{
    if(~f[x][y]) return f[x][y];
    int a[N];
    mm(a,0);
    for(int i=2;i<=x-2;++i) a[sg(i,y)^sg(x-i,y)]=1;
    for(int i=2;i<=y-2;++i) a[sg(x,i)^sg(x,y-i)]=1;
    for(int i=0;;++i) if(!a[i]) return f[x][y]=i;
}
int main(void)
{
    sync;
    mm(f,-1);
    f[2][2]=f[2][3]=f[3][2]=0;
    while(cin>>n>>m)
    {
        if(sg(n,m)) cout<<"WIN"<<endl;
        else cout<<"LOSE"<<endl;
    }
    return 0;
}
//考虑边界!!!
//Think TWICE, Code ONCE!


活动打卡代码 AcWing 244. 谜一样的牛

N00Borz
2个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;
const int N=1e5+10;
int n;
int a[N],b[N],c[N];
inline void add(int p,int x){for(;p<=n;p+=p&-p) c[p]+=x;}
int qry(int p){int res=0;for(;p;p-=p&-p) res+=c[p];return res;}
int main(void)
{
    sync;
    cin>>n;
    add(1,1);
    for(int i=2;i<=n;++i)
    {
        cin>>a[i];
        add(i,1);
    }
    for(int i=n;i>=1;--i)
    {
        int l=1,r=n+1;
        while(l+1<r)
        {
            int m=(l+r)>>1;
            if(qry(m-1)<=a[i]) l=m;
            else r=m;
        }
        // cout<<i<<" "<<l<<" "<<qry(l)<<endl;
        b[i]=l;
        add(l,-1);
    }
    for(int i=1;i<=n;++i)
        cout<<b[i]<<endl;
    return 0;
}
//考虑边界!!!
//Think TWICE, Code ONCE!


活动打卡代码 AcWing 241. 楼兰图腾

N00Borz
2个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;
const int N=2e5+10;
int n;
int a[N],c[N],l[N],r[N];
void add(int p){for(;p<=n;p+=p&-p) c[p]+=1;}
int qry(int p){int res=0;for(;p;p-=p&-p) res+=c[p];return res;}
int main(void)
{
    sync;
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    for(int i=1;i<=n;++i)
    {
        l[i]=qry(a[i]);
        add(a[i]);
    }
    mm(c,0);
    for(int i=n;i>=1;--i)
    {
        r[i]=qry(a[i]);
        add(a[i]);
    }
    ll res=0;
    for(int i=2;i<n;++i) 
        res+=1ll*(i-1-l[i])*(n-i-r[i]);
    cout<<res<<" ";
    res=0;
    for(int i=2;i<n;++i) 
        res+=1ll*l[i]*r[i];
    cout<<res<<endl;
    return 0;
}
//考虑边界!!!
//Think TWICE, Code ONCE!



N00Borz
2个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;
const int N=2e5+10;
int n,m,idx,tot;
int fa[N],dep[N];
struct node{
    int l,r,x;
}q[N*40];
void upd(int &u,int v,int l,int r,int p,int x)
{
    q[u=++tot]=q[v];
    if(l==r) return void(q[u].x=x);
    int m=(l+r)>>1;
    if(p<=m) upd(q[u].l,q[v].l,l,m,p,x);
    else upd(q[u].r,q[v].r,m+1,r,p,x);
}
int qry(int u,int l,int r,int p)
{
    if(l==r) return q[u].x;
    int m=(l+r)>>1;
    if(p<=m) return qry(q[u].l,l,m,p);
    else return qry(q[u].r,m+1,r,p);
}
int f(int x)
{
    int fx=qry(fa[idx-1],1,n,x);
    return fx==0?x:f(fx);
}
void unio(int x,int y)
{
    x=f(x),y=f(y);
    if(x==y)
    {
        fa[idx]=fa[idx-1];
        dep[idx]=dep[idx-1];
    }
    else
    {
        int dx=qry(dep[idx-1],1,n,x);
        int dy=qry(dep[idx-1],1,n,y);
        if(dx<dy)
        {
            upd(fa[idx],fa[idx-1],1,n,x,y);
            dep[idx]=dep[idx-1];
        }
        else if(dx>dy)
        {
            upd(fa[idx],fa[idx-1],1,n,y,x);
            dep[idx]=dep[idx-1];
        }
        else
        {
            upd(fa[idx],fa[idx-1],1,n,x,y);
            upd(dep[idx],dep[idx-1],1,n,y,dx+1);
        }
    }
}
int main(void)
{
    sync;
    cin>>n>>m;
    int res=0;
    while(m--)
    {
        ++idx;
        int op,a,b;
        cin>>op;
        if(op==1)
        {
            cin>>a>>b;
            a^=res,b^=res;
            unio(a,b);
        }
        else if(op==2)
        {
            cin>>a;
            a^=res;
            fa[idx]=fa[a];
            dep[idx]=dep[a];
        }
        else
        {
            cin>>a>>b;
            a^=res,b^=res;
            fa[idx]=fa[idx-1];
            dep[idx]=dep[idx-1];
            res=(f(a)==f(b));
            cout<<res<<endl;
        }
    }
    return 0;
}
//考虑边界!!!
//Think TWICE, Code ONCE!


活动打卡代码 AcWing 198. 反素数

N00Borz
2个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;
int n,res,sum;
int a[10]={2,3,5,7,11,13,17,19,23,29};
void dfs(int p,int pre,int x,int s)
{
    if(s>sum||(s==sum&&x<res))
    {
        res=x;
        sum=s;
    }
    for(int i=1;i<=pre;++i)
    {
        if(1ll*x*a[p]>n) break;
        x*=a[p];
        dfs(p+1,i,x,s*(i+1));
    }
}
int main(void)
{
    sync;
    cin>>n;
    dfs(0,30,1,1);
    cout<<res<<endl;
    return 0;
}
//考虑边界!!!
//Think TWICE, Code ONCE!


活动打卡代码 AcWing 199. 余数之和

N00Borz
2个月前
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#define Debug(in) cout<<#in<<"="<<(in)<<endl
#define mm(a,x) memset(a,x,sizeof(a))
#define mkp(a,b) make_pair(a,b)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sync std::ios::sync_with_stdio(false);std::cin.tie(0)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f,mod=1e9+7;

int main(void)
{
    sync;
    int n,k;
    cin>>n>>k;
    ll res=1ll*n*k;
    for(int l=1,r;l<=n&&k/l;l=r+1)
    {
        r=min(k/(k/l),n);
        res-=1ll*(k/l)*(r-l+1)*(l+r)/2;
    }
    cout<<res<<endl;
    return 0;
}
//考虑边界!!!
//Think TWICE, Code ONCE!


活动打卡代码 AcWing 113. 特殊排序

N00Borz
2个月前
// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int n) {
        vector<int>res;
        res.push_back(1);
        for(int i=2;i<=n;++i)
        {
            int l=0,r=res.size()-1;
            while(l<=r)
            {
                int m=(l+r)>>1;
                if(compare(res[m],i)) l=m+1;
                else r=m-1;
            }
            res.push_back(i);
            for(int j=res.size()-2;j>r;--j)
                swap(res[j],res[j+1]);
        }
        return res;
    }
};