当前位置：
  1. 首页
  2. 全部分类
  3. 数据库
  4. 正文

组队训练记录（8）：2022CCPC威海

数据库 0 0

2022 China Collegiate Programming Contest (CCPC) Weihai Site在这里插入图片描述
在这里插入图片描述
七题977罚时rk49。因为有个队友有事，所以是两个人一机打的。
以下为个人的一些评价
在这里插入图片描述
在这里插入图片描述
现在看其实说8题可写还是保守了，补题应该能补到10题（可能，毕竟接下来三题思路都比较清晰），感觉好久没做这种有一大车能写题的场了，感觉策略和机时都有很大问题。

FPGA底层结构

A. Dunai

模拟，难点在于读懂题意。剩下部分就是一个小贪心。

eip2098 

#include<bits/stdc++.h>
#define int long long 
#define pii pair<int,int>
#define ull unsigned long long
#define endl '\n'
using namespace std;
const int mod=1000000007,N=100005;

int n,m,k,x,l,r;
string s;
set<string>st;
int mx1,mx2;
int cnt1[10],cnt2[10];
void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=5;j++){
            cin>>s;
            st.insert(s);
        }
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>s>>x;
        cnt2[x]++;
        if(st.find(s)!=st.end()){
            cnt1[x]++;
        }
    }
    mx1=cnt1[1]+cnt1[2]+cnt1[3]+cnt1[4]+cnt1[5];
    mx2=min({cnt2[1],cnt2[2],cnt2[3],cnt2[4],cnt2[5]});
    cout<<min(mx1,mx2)<<endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

C. Grass

简单计算几何题。容易证明不共线的五个点一定存在一种合法方案。
所以可以分成以下步骤。

相机权限

  1. 点数小于5直接输出

    N

    O

    NO

    NO

  2. 如果所有点共线 直接输出

    N

    O

    NO

    NO

  3. 找到不共线的五个点，暴力枚举中心点即可。

我写的暴力是

O

(

5

3

)

O(5^3)

O(53)，所以我的复杂度大概是

O

(

n

∗

125

)

O(n*125)

O(n∗125)

keil mdk

注意：暴力枚举时判的是射线同向，而一开始是判是否共直线。

解决方案 

#include<bits/stdc++.h>
#define int long long 
#define pii pair<int,int>
#define ull unsigned long long
#define endl '\n'
using namespace std;
const string yes="YES\n",no="NO\n";
const int mod=1000000007,N=100005;

int n,m,k,l,r;
int x[100005],y[100005];
int dx1,dy1,dx,dy;
bool ck(int x,int y,int xx,int yy){
    return (x*xx>=0)&&(y*yy>=0)&&((x*yy-xx*y)==0);
}
bool ck1(int x,int y,int xx,int yy){
    return ((x*yy-xx*y)==0);
}
vector<int>p,q,ans;
void fk(){
    for(int i=0;i<5;i++){
        int xx=x[ans[i]],yy=y[ans[i]];
        int fg=0;
        for(int j=0;j<5;j++){
            if(j==i)continue;
            for(int k=j+1;k<5;k++){
                if(k==i)continue;
                if(ck(x[ans[j]]-xx,y[ans[j]]-yy,x[ans[k]]-xx,y[ans[k]]-yy)){
                    fg=1;
                }
            }
        }
        if(!fg){
            cout<<xx<<" "<<yy<<endl;
            for(int j=0;j<5;j++){
                if(j!=i){
                    cout<<x[ans[j]]<<" "<<y[ans[j]]<<endl;
                }
            }
            return;
        }
    }
}
void solve(){
    cin>>n;
    p.clear();q.clear();
    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i];
    }
    if(n<5){
        cout<<no;
        return;
    }
    dx1=x[2]-x[1];
    dy1=y[2]-y[1];
    int cnt=0;
    for(int i=3;i<=n;i++){
        if(ck1(dx1,dy1,x[i]-x[1],y[i]-y[1]))cnt++;
        if(ck1(dx1,dy1,x[i]-x[1],y[i]-y[1])){
            p.push_back(i);
        }
        else{
            q.push_back(i);
        }
    }
    if(cnt==n-2){
        cout<<no;
        return;
    }
    ans.clear();
    cout<<yes;
    if(p.size()){
        if(q.size()==1){
            cout<<x[q[0]]<<" "<<y[q[0]]<<endl;
            cout<<x[1]<<" "<<y[1]<<endl;
            cout<<x[2]<<" "<<y[2]<<endl;
            cout<<x[p[0]]<<" "<<y[p[0]]<<endl;
            cout<<x[p[1]]<<" "<<y[p[1]]<<endl;
        }
        else{
            ans.push_back(q[0]);
            ans.push_back(q[1]);
            ans.push_back(1);
            ans.push_back(2);
            ans.push_back(p[0]);
            fk();
        }
    }
    else{
        for(int i=1;i<=5;i++){
            ans.push_back(i);
        }
        fk();
    }

}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
}

D. Sternhalma

大大大分类讨论状压dp。代码中lu表示Left up，rd表示Right down。

opengles 

#include<bits/stdc++.h>
#define int long long 
#define pii pair<int,int>
#define ull unsigned long long
#define endl '\n'
using namespace std;
const string yes="YES\n",no="NO\n";
const int mod=1000000007,N=100005,inf=1e13;
int mp[10][10];
int a[30];
string s[10];
int dp[2000005];
int l[30],r[30],lu[30],ru[30],ld[30],rd[30];
void solve(){
    int now=0;
    string x;
    for(int i=1;i<=5;i++){
        cin>>s[i];
        x+=s[i];
    }
    for(int i=0;i<19;i++){
        if(x[i]=='#'){
            now+=(1<<i);
        }
    }
    cout<<dp[now]<<endl;
}

vector<int>b;
bool cmp(int x,int y){
    return __builtin_popcount(x)<__builtin_popcount(y);
}
signed main(){
    for(int i=1;i<(1<<19);i++){
        dp[i]=-1e9;
    }
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    memset(l,-1,sizeof(l));
    memset(r,-1,sizeof(l));
    memset(lu,-1,sizeof(l));
    memset(ru,-1,sizeof(l));
    memset(ld,-1,sizeof(l));
    memset(rd,-1,sizeof(l));
    for(int i=0;i<19;i++){
        if(i!=0&&i!=3&&i!=7&&i!=12&&i!=16){
            l[i]=i-1;
        }
        if(i!=2&&i!=6&&i!=11&&i!=15&&i!=18){
            r[i]=i+1;
        }
    }
    ld[0]=3;rd[0]=4;
    ld[1]=4;rd[1]=5;
    ld[2]=5;rd[2]=6;
    ld[3]=7;rd[3]=8;
    ld[4]=8;rd[4]=9;
    ld[5]=9;rd[5]=10;
    ld[6]=10;rd[6]=11;
             rd[7]=12;
    ld[8]=12;rd[8]=13;
    ld[9]=13;rd[9]=14;
    ld[10]=14;rd[10]=15;
    ld[11]=15;
              rd[12]=16;
    ld[13]=16;rd[13]=17;
    ld[14]=17;rd[14]=18;
    ld[15]=18;

            ru[3]=0;
    lu[4]=0;ru[4]=1;
    lu[5]=1;ru[5]=2;
    lu[6]=2;
            ru[7]=3;
    lu[8]=3;ru[8]=4;
    lu[9]=4;ru[9]=5;
    lu[10]=5;ru[10]=6;
    lu[11]=6;
    lu[12]=7;ru[12]=8;
    lu[13]=8;ru[13]=9;
    lu[14]=9;ru[14]=10;
    lu[15]=10;ru[15]=11;
    lu[16]=12;ru[16]=13;
    lu[17]=13;ru[17]=14;
    lu[18]=14;ru[18]=15;
    for(int i=0;i<19;i++){
        cin>>a[i];
    }
    int t=1;
    for(int i=1;i<(1<<19);i++){
        b.push_back(i);
    }
    sort(b.begin(),b.end(),cmp);
    for(auto x:b){
        for(int i=0;i<19;i++){
            if(((x>>i)&1)){
                dp[x]=max(dp[x],dp[x-(1<<i)]);
                if(l[i]!=-1&&l[l[i]]!=-1){
                    int j=l[i],k=l[l[i]];
                    if((x>>j&1)&&((x>>k&1)^1)){
                        dp[x]=max(dp[x],dp[x^(1<<i)^(1<<j)^(1<<k)]+a[j]);
                    }
                }
                if(r[i]!=-1&&r[r[i]]!=-1){
                    int j=r[i],k=r[r[i]];
                    if((x>>j&1)&&((x>>k&1)^1)){
                        dp[x]=max(dp[x],dp[x^(1<<i)^(1<<j)^(1<<k)]+a[j]);
                    }
                }
                if(lu[i]!=-1&&lu[lu[i]]!=-1){
                    int j=lu[i],k=lu[lu[i]];
                    if((x>>j&1)&&((x>>k&1)^1)){
                        dp[x]=max(dp[x],dp[x^(1<<i)^(1<<j)^(1<<k)]+a[j]);
                    }
                }
                if(ld[i]!=-1&&ld[ld[i]]!=-1){
                    int j=ld[i],k=ld[ld[i]];
                    if((x>>j&1)&&((x>>k&1)^1)){
                        dp[x]=max(dp[x],dp[x^(1<<i)^(1<<j)^(1<<k)]+a[j]);
                    }
                }
                if(ru[i]!=-1&&ru[ru[i]]!=-1){
                    int j=ru[i],k=ru[ru[i]];
                    if((x>>j&1)&&((x>>k&1)^1)){
                        dp[x]=max(dp[x],dp[x^(1<<i)^(1<<j)^(1<<k)]+a[j]);
                    }
                }
                if(rd[i]!=-1&&rd[rd[i]]!=-1){
                    int j=rd[i],k=rd[rd[i]];
                    if((x>>j&1)&&((x>>k&1)^1)){
                        dp[x]=max(dp[x],dp[x^(1<<i)^(1<<j)^(1<<k)]+a[j]);
                    }
                }
            }
        }
    }
    cin>>t;
    while(t--){
        solve();
    }
}

E. Python Will be Faster than C++

签到。容易发现。如果收敛那么枚举次数一定小于

w

m

a

x

w_{max}

wmax​

Spring的自动装配 

#include<bits/stdc++.h>
#define int long long 
#define pii pair<int,int>
#define ull unsigned long long
#define endl '\n'
using namespace std;
const int mod=1000000007,N=100005;

int n,m,k;
int a[1000005];
void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=n+1;i<=500000;i++){
        a[i]=max(0ll,2*a[i-1]-a[i-2]);
        if(a[i]<k){
            cout<<"Python 3."<<i<<" will be faster than C++";
            return ;
        }
    }
    cout<<"Python will never be faster than C++";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}

G. Grade 2

将

k

k

k 拆成

a

t

+

b

at+b

at+b ,则题目中所给

k

x

⊕

x

kx \oplus x

kx⊕x 就变成

(

a

t

x

+

b

x

)

⊕

x

(atx+bx) \oplus x

(atx+bx)⊕x 。容易发现当

t

t

t 取大于

x

x

x 的最小2的幂次时，

g

c

d

(

a

t

x

,

x

)

=

x

gcd(atx,x) = x

gcd(atx,x)=x 。发现此结论后打表前缀和优化即可。

hyperledger 

#include<bits/stdc++.h>
#define int long long 
#define pii pair<int,int>
#define ull unsigned long long
#define endl '\n'
using namespace std;
const int mod=1000000007,N=100005;

int n,m,k,x,l,r;
int a[2000005];
void main_init(){
    n=(1<<(__lg(x)+1));
    for(int i=1;i<=n;i++){
        int d=((i*x)^x);
        int k=(__gcd(d,x)==1);
        a[i]=k+a[i-1];
    }
}
int getans(int x){
    return x/n*a[n]+a[x%n];
}
void solve(){
    cin>>l>>r;
    if(x==1){
        cout<<r-l+1<<endl;
        return;
    }
    cout<<getans(r)-getans(l-1)<<endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>x>>t;
    main_init();
    while(t--){
        solve();
    }
}

I. Dragon Bloodline

二分答案+贪心选择。 我的写法是会爆ll的，而且我的复杂度是

O

(

n

k

l

o

g

n

l

o

g

1

e

15

)

O(nklogn log1e15)

O(nklognlog1e15) 的__int128。
但是它过了。。。。
注意二分上界，一开始只开了1e15一直wa。

access_token失效 

#include<bits/stdc++.h>
#define int long long 
#define pii pair<int,int>
#define ull unsigned long long
#define endl '\n'
using namespace std;
const string yes="YES\n",no="NO\n";
const int mod=1000000007,N=100005,inf=1e13;
int n,k;
int a[100005],b[105],c[105],need[100005];


__int128 f[100005],g[105];
int mxsum;
bool ck(__int128 x){
    __int128 needsum=0,o=x;
    for(int i=1;i<=n;i++){
        needsum+=o*a[i];
        if(needsum>mxsum)return false;
        f[i]=a[i]*x;
    }
    for(int i=1;i<=k;i++){
        g[i]=b[i];
    }
    for(int i=k;i;i--){
        sort(f+1,f+1+n);
        for(int j=n;g[i]&&j&&f[j];j--){
            int t=f[j]/c[i];
            if(t>g[i]){
                f[j]-=c[i]*g[i];
                g[i]=0;
            }
            else{
                f[j]-=c[i]*t;
                g[i]-=t;
            }
        }
        sort(f+1,f+1+n);

        for(int j=n;g[i];j--){
            if(f[j]){
                f[j]=0;
                g[i]--;
            }
            else{
                return true;
            }
        }
    }
    for(int i=1;i<=n;i++){
        if(f[i])return false;
    }
    return true;
}
void solve(){
    cin>>n>>k;
    mxsum=0;
    int sum=0,sumb=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    for(int i=1;i<=k;i++){
        cin>>b[i];
        sumb+=b[i];
        mxsum+=(1<<(i-1))*b[i];
    }
    sort(a+1,a+1+n);
    int l=1,r=1e17;
    while(l<=r){
        int mid=(l+r)/2;
        if(ck(mid)){
            l=mid+1;
        }
        else{
            r=mid-1;
        }
    }
    cout<<r<<endl;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    for(int i=1;i<=25;i++){
        c[i]=(1<<(i-1));
    }
    while(t--){
        solve();
    }
}

J. Eat, Sleep, Repeat

最终结果是唯一确定的，每轮只能选一个数。操作步数就是一开始的和减去最终最终结果的和。
找到最终结果即可。

Unity小技巧 

#include<bits/stdc++.h>
#define int long long 
#define pii pair<int,int>
#define ull unsigned long long
#define endl '\n'
using namespace std;
const string yes="YES\n",no="NO\n";
const int mod=1000000007,N=100005,inf=1e15;

int n,m,k,l,r,sum;
int a[100005];
pii q[100005];
map<int,int>mp;
vector<int>q0;
int erfen(int x){
    int l=1,r=n;
    while(l<=r){
        int mid=(l+r)/2;
        if(a[mid]>=x){
            r=mid-1;
        }
        else{
            l=mid+1;
        }
    }
    return r;
}
void solve(){
    cin>>n>>k;
    sum=0;
    mp.clear();q0.clear();
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    q[0]={-1,0};
    q[k+1]={inf,0};
    q0.push_back(-1);
    q0.push_back(inf);
    for(int i=1;i<=k;i++){
        cin>>q[i].first>>q[i].second;
        if(q[i].second==0){
            q0.push_back(q[i].first);
        }
    }
    k++;
    sort(q0.begin(),q0.end());
    sort(a+1,a+1+n);
    sort(q+1,q+1+k);
    mp[-1]=0;
    for(int i=1;i<=k;i++){
        if(q[i].first!=q[i-1].first){
            mp[q[i-1].first+1]=inf;
        }
        mp[q[i].first]=q[i].second;
    }
    for(int i=1;i<q0.size();i++){
        int l=q0[i-1],r=q0[i];
        int res=erfen(r)-erfen(l);
        for(int now=l+1;res;){
            if(res>mp[now]){
                res-=mp[now];
                sum-=now*mp[now];
            }
            else{
                sum-=res*now;
                res=0;
            }
            now++;
        }
    }
    //cout<<sum<<"!!!\n";
    if(sum%2){
        cout<<"Pico\n";
    }
    else{
        cout<<"FuuFuu\n";
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
}
上一篇 迷你主机安装openwrt软路由系统（附启动盘制作教程+ISO、IMG镜像文件）
下一篇 GEE：对NDVI的时间序列使用Sen+MK趋势检验

相关文章

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

插入图片
浏览器会保存昵称、邮箱和网站cookies信息，下次评论时使用。