头像

Lazy_tiger

ACM




离线:3天前


活动打卡代码 AcWing 104. 货仓选址

Lazy_tiger
7个月前
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <list>
#include <limits.h>
#define il inline
#define pf printf
#define sf(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3fll
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int dx[4]= {0,-1,0,1},dy[4]= {-1,0,1,0};
int dx8[8] = {0, 0, 1, -1, -1, -1, 1, 1}, dy8[8] = {1, -1, 0, 0, -1, 1, -1, 1};
int gcd(int a,int b)
{
    return b? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}
int readint()
{
    int x;
    scanf("%d", &x);
    return x;
}
const int N=2e6+10;
int a[N];
int main()
{
    ios;
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    int mid=a[(n+1)/2];
    ll sum=0;
    for(int i=1;i<=n;i++) sum+=abs(a[i]-mid);
    cout<<sum<<endl;
    return 0;
}



活动打卡代码 AcWing 103. 电影

Lazy_tiger
7个月前
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <list>
#include <limits.h>
#define il inline
#define pf printf
#define sf(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3fll
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int dx[4]= {0,-1,0,1},dy[4]= {-1,0,1,0};
int dx8[8] = {0, 0, 1, -1, -1, -1, 1, 1}, dy8[8] = {1, -1, 0, 0, -1, 1, -1, 1};
/*
int get_bitz(unsigned int x){return _builtin_ctz(x);}
int get_bitzll(unsigned int x){return _builtin_ctzll(x);}
int get_bitcount(unsigned int x){return _builtin_popcount(x);}
int get_bitcountll(unsigned int x){return _builtin_popcountll(x);}
*/
int gcd(int a,int b)
{
    return b? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}
int readint()
{
    int x;
    scanf("%d", &x);
    return x;
}
const int N=200020;
int n,m;
int ans,ans_n,ans_m,a[N];
map<int,int> mp;
int main()
{
    ios;
    scanf("%d",&n);
    rep(i,1,n)
    {
        int x=readint();
        mp[x]++;
    }
    scanf("%d",&n);
    rep(i,1,n) cin>>a[i];

    rep(i,1,n)
    {
        int x=readint();
        if(mp[a[i]]>ans_n ||(mp[a[i]]==ans_n && mp[x]>ans_m))
            ans=i,ans_n=mp[a[i]],ans_m=mp[x];
    }
    printf("%d \n",ans);
    return 0;
}



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

Lazy_tiger
7个月前
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <vector>
#define LL long long
#define INF 0x3f3f3f3f
#define PII pair<int,int>
#define PB push_back
#define POP pop_back()
#define FI first
#define SE second
#define ULL unsigned long long
using namespace std;
const double pi = acos(-1),eps=1e-8;
//const int maxn = 1 << 17;
const int N = 1000,NN = 1e7 + 1, M = 1 << 16, mod = 1e9 + 7;

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



活动打卡代码 AcWing 102. 最佳牛围栏

Lazy_tiger
7个月前

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

define il inline

define pf printf

define sf(x) scanf(“%d”, &x)

define scs(x) scanf(“%s”, x)

define scl(x) scanf(“%lld”, &x)

define mst(a,x) memset(a, x, sizeof(a))

define rep(i,a,b) for(int i=a;i<=b;i++)

define dep(i,e,s) for(int i=(e); i>=(s); –i)

define ll long long

define ull unsigned long long

define PII pair[HTML_REMOVED]

define inf 0x3f3f3f3f

define infll 0x3f3f3f3f3f3fll

define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

using namespace std;
int dx[4]= {0,-1,0,1},dy[4]= {-1,0,1,0};
int dx8[8] = {0, 0, 1, -1, -1, -1, 1, 1}, dy8[8] = {1, -1, 0, 0, -1, 1, -1, 1};
/
int get_bitz(unsigned int x){return _builtin_ctz(x);}
int get_bitzll(unsigned int x){return _builtin_ctzll(x);}
int get_bitcount(unsigned int x){return _builtin_popcount(x);}
int get_bitcountll(unsigned int x){return _builtin_popcountll(x);}
/
int gcd(int a,int b)
{
return b? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
return a*b/gcd(a,b);
}
const int N=2e6+10;
int n , F;
double a[N],s[N];
bool check(double x)
{
rep(i,1,n) s[i]=s[i-1]+a[i]-x;

double mins=0;
for(int k=F;k<=n;k++)
{
    mins=min(mins,s[k-F]);
    if(s[k]>mins)
        return true;
}
return false;

}
int main()
{
ios;
cin>>n>>F;
double l=0,r=0;
rep(i,1,n)
{
cin>>a[i];
r=max(r,a[i]);
}
while(r-l>1e-5)
{
double mid=(l+r)/2;
if(check(mid)) l=mid;
else r=mid;
}
cout<<(int)(r*1000)<<endl;

return 0;

}

```



活动打卡代码 AcWing 101. 最高的牛

Lazy_tiger
8个月前
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <list>
#include <limits.h>
#define il inline
#define pf printf
#define sf(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3fll
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int dx[4]= {0,-1,0,1},dy[4]= {-1,0,1,0};
int dx8[8] = {0, 0, 1, -1, -1, -1, 1, 1}, dy8[8] = {1, -1, 0, 0, -1, 1, -1, 1};
/*
int get_bitz(unsigned int x){return _builtin_ctz(x);}
int get_bitzll(unsigned int x){return _builtin_ctzll(x);}
int get_bitcount(unsigned int x){return _builtin_popcount(x);}
int get_bitcountll(unsigned int x){return _builtin_popcountll(x);}
*/
int gcd(int a,int b)
{
    return b? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}
const int N=2e5+10,mod=9901;

struct node
{
    int idx,x;
} nd[N];

int cmp(node a,node b)
{
    return a.x<b.x;
}
int n,p,h,m;
int c[N],d[N];
map<PII,bool> existed;
int main()
{
    ios;
    cin>>n>>p>>h>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        if(a>b) swap(a,b);
        if(existed[make_pair(a,b)]) continue;
        d[a+1]--,d[b]++;
        existed[make_pair(a,b)]=true;
    }
    for(int i=1;i<=n;i++)
    {
        c[i]=c[i-1]+d[i];
        cout<<h+c[i]<<endl;
    }
    return 0;
}



活动打卡代码 AcWing 100. IncDec序列

Lazy_tiger
8个月前
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <list>
#include <limits.h>
#define il inline
#define pf printf
#define sf(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3fll
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int dx[4]= {0,-1,0,1},dy[4]= {-1,0,1,0};
int dx8[8] = {0, 0, 1, -1, -1, -1, 1, 1}, dy8[8] = {1, -1, 0, 0, -1, 1, -1, 1};
/*
int get_bitz(unsigned int x){return _builtin_ctz(x);}
int get_bitzll(unsigned int x){return _builtin_ctzll(x);}
int get_bitcount(unsigned int x){return _builtin_popcount(x);}
int get_bitcountll(unsigned int x){return _builtin_popcountll(x);}
*/
int gcd(int a,int b)
{
    return b? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}
const int N=2e5+10,mod=9901;

struct node
{
    int idx,x;
} nd[N];

int cmp(node a,node b)
{
    return a.x<b.x;
}
int n;
ll a[N];
int main()
{
    ios;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    ll p=0,q=0;
    for(int i=2;i<=n;i++)
    {
        ll t=a[i]-a[i-1];
        if(t>0)
        {
            p+=t;
        }
        else
            q-=t;
    }
    cout<<max(p,q)<<endl;
    cout<<abs(p-q)+1<<endl;
    return 0;
}



活动打卡代码 AcWing 97. 约数之和

Lazy_tiger
8个月前
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <list>
#include <limits.h>
#define il inline
#define pf printf
#define sf(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3fll
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int dx[4]= {0,-1,0,1},dy[4]= {-1,0,1,0};
int dx8[8] = {0, 0, 1, -1, -1, -1, 1, 1}, dy8[8] = {1, -1, 0, 0, -1, 1, -1, 1};
/*
int get_bitz(unsigned int x){return _builtin_ctz(x);}
int get_bitzll(unsigned int x){return _builtin_ctzll(x);}
int get_bitcount(unsigned int x){return _builtin_popcount(x);}
int get_bitcountll(unsigned int x){return _builtin_popcountll(x);}
*/
int gcd(int a,int b)
{
    return b? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}
const int N=5e5+10,mod=9901;

ll qmi(ll a,ll k)
{
    ll res=1;
    a%=mod;//a可能比较大
    while(k)
    {
        if(k&1) res=res*a%mod;
        a=a*a%mod;
        k>>=1;
    }
    return res;
}

ll sum(ll p,ll k)
{
    if(k==1) return 1;
    if(k%2==0) return (1+qmi(p,k/2))*sum(p,k/2)%mod;
    return (sum(p,k-1)+qmi(p,k-1))%mod;
}

int main()
{
    ios;
    ll a,b;
    cin>>a>>b;
    //对a分解质因数
    int res=1;
    for(int i=2;i*i<=a;i++)
    {
        if(a%i==0)
        {
            int s=0;
            while(a%i==0)
            {
                a/=i,s++;
            }
            res=res*sum(i,b*s+1)%mod;
        }
    }
    if(a>1) res=res%mod*sum(a,b+1)%mod;
    if(a==0) res=0;
    cout<<res<<endl;
    return 0;
}



活动打卡代码 AcWing 844. 走迷宫

Lazy_tiger
8个月前
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <list>
#include <limits.h>
#define il inline
#define pf printf
#define sf(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3fll
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int dx[4]= {0,-1,0,1},dy[4]= {-1,0,1,0};
int dx8[8] = {0, 0, 1, -1, -1, -1, 1, 1}, dy8[8] = {1, -1, 0, 0, -1, 1, -1, 1};
/*
int get_bitz(unsigned int x){return _builtin_ctz(x);}
int get_bitzll(unsigned int x){return _builtin_ctzll(x);}
int get_bitcount(unsigned int x){return _builtin_popcount(x);}
int get_bitcountll(unsigned int x){return _builtin_popcountll(x);}
*/
int gcd(int a,int b)
{
    return b? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}
const int N=110,mod=1e9+10;
int n,m;
int g[N][N],d[N][N];

void bfs()
{
    memset(d,-1,sizeof(d));
    queue<PII> q;
    q.push({0,0});
    d[0][0] = 0 ;

    while(q.size())
    {
        PII t = q.front();
        q.pop();
        for(int i = 0 ;i < 4 ; i ++ )
        {
            int x = dx[i] + t.first , y = dy[i] + t.second;
            if(x >= 0 && x < n && y >=0 && y < m && d[x][y] == -1 && g[x][y] == 0)
            {
                d[x][y] = d[t.first][t.second] + 1;
                q.push({x,y});
            }
        }
    }

    cout<<d[n-1][m-1]<<endl;
    return ;
}
int main()
{
    ios;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>g[i][j];
        }
    }
    bfs();
    return 0;
}



活动打卡代码 AcWing 843. n-皇后问题

Lazy_tiger
8个月前
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <list>
#include <limits.h>
#define il inline
#define pf printf
#define sf(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3fll
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int dx[4]= {0,-1,0,1},dy[4]= {-1,0,1,0};
int dx8[8] = {0, 0, 1, -1, -1, -1, 1, 1}, dy8[8] = {1, -1, 0, 0, -1, 1, -1, 1};
/*
int get_bitz(unsigned int x){return _builtin_ctz(x);}
int get_bitzll(unsigned int x){return _builtin_ctzll(x);}
int get_bitcount(unsigned int x){return _builtin_popcount(x);}
int get_bitcountll(unsigned int x){return _builtin_popcountll(x);}
*/
int gcd(int a,int b)
{
    return b? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}
const int N=110,mod=1e9+10;
int n;
int dg[N],udg[N],col[N];
char g[N][N];

void dfs(int u)
{
    if(u==n)//表示已经搜索了n行
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cout<<g[i][j];
            }
            cout<<endl;
        }
        cout<<endl;
        return ;
    }
    for(int i=0;i<n;i++)//选择了多少
    {
        if(!col[i]&&!dg[i+u]&&!udg[n-u+i])
        {
            col[i]=dg[i+u]=udg[n-u+i]=true;
            g[u][i]='Q';
            dfs(u+1);
            g[u][i]='.';
            col[i]=dg[i+u]=udg[n-u+i]=false;
        }
    }
}

int main()
{
    ios;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            g[i][j]='.';
        }
    }
    dfs(0);
    return 0;
}



活动打卡代码 AcWing 842. 排列数字

Lazy_tiger
8个月前
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <cstdio>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <iomanip>
#include <list>
#include <limits.h>
#define il inline
#define pf printf
#define sf(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,e,s) for(int i=(e); i>=(s); --i)
#define ll long long
#define ull unsigned long long
#define PII pair<int,int>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3fll
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
int dx[4]= {0,-1,0,1},dy[4]= {-1,0,1,0};
int dx8[8] = {0, 0, 1, -1, -1, -1, 1, 1}, dy8[8] = {1, -1, 0, 0, -1, 1, -1, 1};
/*
int get_bitz(unsigned int x){return _builtin_ctz(x);}
int get_bitzll(unsigned int x){return _builtin_ctzll(x);}
int get_bitcount(unsigned int x){return _builtin_popcount(x);}
int get_bitcountll(unsigned int x){return _builtin_popcountll(x);}
*/
int gcd(int a,int b)
{
    return b? gcd(b,a%b) : a;
}
int lcm(int a,int b)
{
    return a*b/gcd(a,b);
}
const int N=2e6+10,mod=1e9+10;
int n;
int p[N];
bool st[N];

void dfs(int u)
{
    if(u==n)
    {
        for(int i=0;i<n;i++)
        {
            cout<<p[i]<<" ";
        }
        cout<<endl;
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(!st[i])
        {
            st[i]=true;
            p[u]=i;
            dfs(u+1);
            p[u]=0;
            st[i]=false;
        }
    }
}
int main()
{
    ios;
    cin>>n;
    dfs(0);
    return 0;
}