你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

2021-11-15 (2019 CCPC网络选拔赛)

2021-11-18 6:11:30

A - ^&^

题意:

t组样例,每组样例给你一个A和B,你需要求一个最小的C使得(A  xor  C)  &  (B  xor  C)的值最小。

思路:

em....乘法分配律?提取出A和B先进行与(&)操作,然后在异或C,因为异或相同为0,不同为1,你想要最小的肯定C要等于A&B,这里注意,如果求出的C=0,要输出1。

代码:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)
    {
        long long ans;
        long long a,b;
        cin>>a>>b;
        ans=a&b;
        if(ans==0)
            cout<<1<<endl;
        else
            cout<<ans<<endl;
    }
}

F - Shuffle Card

题意:

给你两个数n和m,你现在有n个从1到n的卡片,接下来你有m个操作,每个操作输入一 个卡片数字,接下来你要把这个数字提到第一位,其他的依次往后退,输出m个操作后卡片的顺序。

思路:

a[i]存一下卡片,用vis[i] 去标记a[i] 数组的每个数,m个操作可以发现,你从后往前存入b数组不就是这个卡片的顺序了么,因为是从后往前执行的操作,这其中已经放在开头的将其vis[i]标记为0代表已经存过了,当你存完这m个操作提前的卡片数字后(存完的vis[i]都标记为0了),剩下的(即vis[i]为1)依次存放即可。注意:它输出时每个数字后都要有一个空格,并且不能换行,这两个坑都踩了QAQ。

代码:

#include<bits/stdc++.h>
using namespace std;
int a[100005],b[100005],op[100005],vis[100005];
int main()
{
    ios::sync_with_stdio(false);
    memset(vis,0,sizeof(vis));
    long long ans;
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];
        vis[a[i]]=1;
    }
    for(int i=1; i<=m; i++)
        cin>>op[i];
    int k=1;
    for(int i=m; i>=1; i--)
    {
        if(vis[op[i]])
        {
            b[k++]=op[i];
            vis[op[i]]=0;
        }
    }

    for(int i=1; i<=n; i++)
    {
        if(vis[a[i]])
        {
            b[k++]=a[i];
            vis[a[i]]=0;
        }
    }

    for(int i=1; i<=n; i++)
    {
        cout<<b[i]<<" ";
    }
    
}

G - Windows Of CCPC 

题意:

输入一个n,找出对应的图案。

n=1
CC
PC

n=2
CCCC
PCPC
PPCC
CPPC

n=3
CCCCCCCC
PCPCPCPC
PPCCPPCC
CPPCCPPC
PPPPCCCC
CPCPPCPC
CCPPPPCC
PCCPCPPC

思路:

模拟,就是将图案复制四份,而在左下角的全部取反(即P为C,C为P)。

因为n=1 是2阶矩阵,n=2 是4阶矩阵,n=3 是8阶矩阵

所以每个矩阵大小为2的n次方

假设我们将第一阶窗口化为4个区,可以发现1、2、4区的符号是一样的,第三个区与其他区符号是‘相反’的(C就转为P,P就转为C)。
在第二阶及以上的情况下,我们可以知道它是以上一阶窗口为基础,将上一阶窗口认为是1区,各区之间的关系与一阶相似。注意,第三区的所有符号都要与其他区的符号‘相反’。

三阶及以上阶窗口与上面推导过程相似。
由于题目的数据比较小,所以我们就可以直接用数组预处理,到时候直接输出就好了。需要注意的是,我们可以发现每一阶窗口的大小是2的k次方(k为阶数)。所以第2区的横坐标范围是从2的(k次方-1)+1 ~ 2的k次方,纵坐标范围是从1 ~ 2的k次方-1(博主把初始化起点定为1)。其他区与此类似。

代码:

#include<iostream>
#include<cmath>
using namespace std;
const int MAX = 1024+5;
char mp[MAX][MAX];

int main(void)
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        mp[1][1] = 'C'; //初始化最原始的左上角
        mp[1][2] = 'C';
        mp[2][1] = 'P';
        mp[2][2] = 'C';

        int k = 1;//阶数
        for(int i=1; i<=n; i++)
        {
            int x1 = pow(2,k);
            int x2 = pow(2,k-1);

            for(int i=1; i<=x2; i++) //右上角 (以左上角为参照,即纵坐标-x2位置赋值给当前位置)
            {
                for(int j=x2 + 1; j<=x1; j++)
                {
                    mp[i][j] = mp[i][j-x2];
                }
            }

            for(int i=x2 + 1; i<=x1; i++) //右下角 (以右上角为参照,即横坐标-x2位置赋值给当前位置)
            {
                for(int j=x2 + 1; j<=x1; j++)
                {
                    mp[i][j] = mp[i-x2][j];
                }
            }

            for(int i=x2 + 1; i<=x1; i++) //左下角 (以左上角为参照,即纵坐标-x2位置翻转赋值给当前位置)
            {
                for(int j=1; j<=x2; j++)
                {
                    if(mp[i-x2][j] == 'C')
                    {
                        mp[i][j] = 'P';
                    }
                    if(mp[i-x2][j] == 'P')
                    {
                        mp[i][j] = 'C';
                    }
                }
            }
            k++; 
        }

        int x = pow(2,n);
        for(int i=1; i<=x; i++)
        {
            for(int j=1; j<=x; j++)
            {
                cout << mp[i][j];
            }
            cout << endl;
        }
    }
    return 0;
}

H - Fishing Master

题意:

有n条鱼,每条鱼要煮相应的时间才能吃,捕一条鱼的时间是相同的,在捕鱼的时间内不能做其他事,可以捕多条鱼,求把所有的鱼都煮熟需要多少时间。

思路:

首先我们第一次捕鱼和所有的炖鱼时间都要计入答案,再煮鱼的时候我们可以去选择钓鱼,但是我们最多钓a[i]/k条鱼,此时我们有一个选择就是,要不要多花k-(a[i]%k)的时间去多钓一条鱼,仔细思考一下,就是如果我们随后不缺鱼可炖,肯定不需要多花这个时间,但是万一我们后边缺鱼了,那么我们必须多花这个时间,所以,我们把这个时间入一个优先队列,如果后边需要煮鱼但是手里鱼数量不够了,此时必须去前边多花一点时间换一条鱼,取队首就好了。

题解:

 代码:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN = 1e5+5;
ll a[MAXN];

priority_queue<ll,vector<ll>,greater<ll> >q;
bool cmp(ll a,ll b)
{
    return a>b;
}

int main()
{
    ll t,n,k;
    scanf("%lld",&t);
    while(t--)
    {
        while(!q.empty())
            q.pop();
        scanf("%lld%lld",&n,&k);
        for(ll i=1; i<=n; i++)
            scanf("%lld",&a[i]);
        sort(a+1,a+n+1,cmp);
        ll ans=k,num=1;
        for(ll i=1; i<=n; i++)
        {
            ans+=a[i];
            if(num>=i)
            {
                num+=a[i]/k;
                q.push(k-(a[i]%k));
                continue;
            }
            if(q.empty())
                ans+=k;
            else
            {
                ans+=q.top();
                q.pop();
            }
            num+=a[i]/k;
            q.push(k-(a[i]%k));
        }
        printf("%lld\n",ans);
    }
    return 0;
}

D - path

题意:

无向图,n个点,m条有权边,求第k短的路径多长。

思路:

bfs,要注意的是,如果扩展每个可以到达的点,一定会超时+爆栈,其实这样做是没有必要的,每一次只用扩展同一层的点以及所有连边中最小的所指向的那个点。

先把全部的边入队列,然后再往外bfs。每次取队首,然后接上一个点,再塞回去,把查询离线,然后记录前max(k)取队首,就可以O(1)访问了。

直接优先队列模拟的话,会被菊花图卡时间和空间,所以要加一个优化,优先队列改用set,保证每次set里最多只有max(k)个元素
 

题解:

 代码:


#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const ll MAXN = 5e4+5;
const ll MOD = 1e9+7;
struct node
{
    ll x,y;
    ll val;
    bool operator <(const node &r)const
    {
        return val<r.val;
    }
} a,b;
multiset<node>s;
struct nod
{
    ll to,val;
} p;
vector<nod>v[MAXN],g[MAXN];
ll ans[MAXN],c[MAXN];
bool cmp(nod a,nod b)
{
    return a.val<b.val;
}
int main()
{
    ll t,n,m,Q,u,V,w;
    scanf("%lld",&t);
    while(t--)
    {
        ll maxx=0;
        scanf("%lld%lld%lld",&n,&m,&Q);
        s.clear();
        for(ll i=1; i<=n; i++)
            v[i].clear();
        while(m--)
        {
            scanf("%lld%lld%lld",&u,&V,&w);
            p.to=V,p.val=w;
            v[u].push_back(p);
            a.x=u,a.y=V;
            a.val=w;
            s.insert(a);
        }
        for(ll i=1; i<=n; i++)
            sort(v[i].begin(),v[i].end(),cmp);
        for(ll i=1; i<=Q; i++)
        {
            scanf("%lld",&c[i]);
            maxx=max(maxx,c[i]);
        }
        ll pos=0;
        multiset<node>::iterator it;
        while(!s.empty())
        {
            a=*s.begin();
            s.erase(s.begin());
            ans[++pos]=a.val;
            if(pos==maxx)break;
            int len=v[a.y].size();
            for(ll i=0; i<=len-1; i++)
            {
                b=a;
                b.y=v[a.y][i].to;
                b.val+=v[a.y][i].val;
                if(s.size()>maxx-pos)
                {
                    it=s.end();
                    it--;
                    if((*it).val>b.val)
                    {
                        s.erase(it);
                        s.insert(b);
                    }
                    else break;
                }
                else
                {
                    s.insert(b);
                }
            }

        }
        for(ll i=1; i<=Q; i++)
        {
            printf("%lld\n",ans[c[i]]);
        }
    }
    return 0;
}