UPC2018组队训练赛第三场

2023-11-03 05:30

本文主要是介绍UPC2018组队训练赛第三场,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目来自BAPC2017 Preliminaries


 

A题:Abandoned Animal

最后输入的m个字符串是sister按顺序买的物品(保证买的物品不重复),首先输入的k行数据(i,s)代表第i个商店所卖的物品s,保证每个商店卖的物品不同。问sister买的物品所在的商店的编号是不是一个非递减的序列。如果不是输出"impossible",如果是并且这个商店的编号序列是唯一的,输出"unique",否则输出"ambiguous".

我们可以首先对商店的信息按照商店的编号从小到大排序,用a[]数组存储每个商店第一件物品的下标,用b[]数组存储每个商店最后一件物品的下标

第一次首先按照sister的顺序对她买的物品去寻找商店的编号,记下当前商店第一件物品的下标,下次寻找时,从该下标开始往后寻找。如果当前寻找操作找不到对应的商店,则输出“impossible”。否则再倒着按着sister的顺序倒着去寻找商店的编号。如果两次寻找后的序列一样,输出“unique”,否则输出“ambiguous".

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct node
 4 {
 5     int pos;
 6     string s;
 7 }mp[100005];
 8 bool cmp(node a,node b)
 9 {
10     return a.pos<b.pos;
11 }
12 int n,k,m;
13 string t[100005];
14 int a[100005],b[100005],Left[100005],Right[100005];
15 int main()
16 {
17 //    freopen("in.txt","r",stdin);
18     ios::sync_with_stdio(false);
19     cin.tie(0);
20     cin>>n>>k;
21     for(int i=0;i<k;i++)
22     {
23         cin>>mp[i].pos>>mp[i].s;
24     }
25     sort(mp,mp+k,cmp);
26     for(int i=k-1;i>=0;i--)
27         a[mp[i].pos]=i;
28     for(int i=0;i<k;i++)
29         b[mp[i].pos]=i;
30     cin>>m;
31     int now=a[0],flag,ff=0;
32     for(int i=0;i<m;i++)
33     {
34         cin>>t[i];
35         if(ff)  continue;
36         flag=0;
37         for(int j=now;j<k;j++)
38         {
39             if(t[i]==mp[j].s)
40             {
41                 Left[i]=mp[j].pos;
42                 now=a[mp[j].pos];
43                 flag=1;
44                 break;
45             }
46         }
47         if(!flag)    ff=1;
48     }
49     if(ff)
50     {
51         cout<<"impossible"<<endl;
52         return 0;
53     }
54     now=k-1;
55     for(int i=m-1;i>=0;i--)
56     {
57         for(int j=now;j>=0;j--)
58         {
59             if(t[i]==mp[j].s)
60             {
61                 Right[i]=mp[j].pos;
62                 now=b[mp[j].pos];
63                 break;
64             }
65         }
66         if(Right[i]!=Left[i])
67         {
68             cout<<"ambiguous"<<endl;
69             return 0;
70         }
71     }
72     cout<<"unique"<<endl;
73     return 0;
74 }
View Code

 

 B题:Booming Business

  

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int mod=1e9+7;
 4 typedef long long ll;
 5 ll f[400][400];
 6 int main()
 7 {
 8     int h,w;
 9     scanf("%d%d",&h,&w);
10     f[1][1]=1;
11     for(int i=2;i<=h;i++)
12     {
13         f[1][i]=1;
14         for(int j=2;j<=w;j++)
15         {
16             for(int k=1;k<=j-1;k++)
17                 f[j][i]=(f[j][i]%mod+f[k][i-1]%mod*f[j-k][i]%mod)%mod;
18         }
19     }
20     ll ans=(f[w][h]-f[w][h-1]+mod)%mod;
21     printf("%lld\n",ans);
22     return 0;
23 }
View Code

 

C题:Crowd Control

待更新。。。


 

D题:Disastrous Doubling

不需要大数,可以直接处理。当细菌的数量>=输入数据的最大值时才开始取模

 

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 const int N=1e5+10;
 6 const int mod=1e9+7;
 7 int n;
 8 bool flag;
 9 int main()
10 {
11     scanf("%d",&n);
12     ll ans=1,tmp=1ll<<61,x;
13     for (int i=1;i<=n;i++)
14     {
15         scanf("%lld",&x);
16 
17         if (!flag)
18         {
19             ans=ans*2;
20             if (ans>=tmp) flag=1;
21             ans=ans-x;
22             if (ans<0)
23             {
24                 printf("error\n");
25                 return 0;
26             }
27         }
28         else ans=(ans*2%mod-x%mod+mod)%mod;
29     }
30     printf("%lld\n",ans%mod);
31     return 0;
32 }
View Code

 

E题:Envious Exponents

输入n和k,求k个2的不同次幂的和,满足它是最小的大于n的数。

把n转化成二进制,然后就在二进制中找k个1,使其满足条件。

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 typedef long long ll;
 5 int a[1000];
 6 ll n;
 7 ll k;
 8 int main()
 9 {
10     scanf("%lld %lld",&n,&k);
11     ll nn=n;
12     int cnt=0;
13     while(nn)
14     {
15         a[cnt++]=nn%2;
16         nn/=2;
17     }
18     int cnt1=0,flag=0,pos;
19     for(int i=cnt-1;i>=0;i--)
20     {
21         if(a[i]==1)
22         {
23             cnt1++;
24             pos=i;
25         }
26         if(cnt1==k)
27         {
28             flag=1;
29             a[i]=0;
30             break;
31         }
32     }
33     if(!flag) //1 is not enough
34     {
35             for(int i=0;i<cnt;i++)  //从最低位到最高位把0变成1,如果1的个数还不满足k个,就增加位数添加1
36             {
37                 if(a[i]==0){
38                     a[i]=1;
39                     cnt1++;
40                 }
41                 if(cnt1==k)
42                     break;
43             }
44             while(cnt1<k)
45             {
46                 a[cnt++]=1;
47                 cnt1++;
48             }
49     }
50     else //1 is enough
51     {
52         for(int i=0;i<pos;i++)  //0到pos都变成0
53             a[i]=0;
54         int flag1=0,pos1;
55         for(int i=pos+1;i<cnt;i++) //从pos开始到最高位,把第一个0变成1,并且把该位置后面的所有1都移到低位
56         {
57             if(a[i]==0)
58             {
59                 a[i]=1;
60                 flag1=1;
61                 pos1=i;
62                 break;
63             }
64         }
65         if(!flag1)
66         {
67             a[cnt++]=1;
68             for(int i=cnt-2;i>=k-1;i--)
69                 a[i]=0;
70             for(int i=0;i<k-1;i++)
71                 a[i]=1;
72         }
73         else
74         {
75             int cnt2=0;
76             for(int i=cnt-1;i>=pos1;i--)
77                 if(a[i]==1) cnt2++;
78             for(int i=0;i<k-cnt2;i++)
79                 a[i]=1;
80             for(int i=k-cnt2;i<pos1;i++)
81                 a[i]=0;
82         }
83     }
84     ll ans=0;
85     ll p=1;
86     for(int i=0;i<cnt;i++)
87     {
88         ans+=p*(ll)a[i];
89         p*=2;
90     }
91     printf("%lld\n",ans);
92     return 0;
93 }
View Code

 

H题:Horror Film Night

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e6+5;
 4 struct node
 5 {
 6     bool pre1,pre2;
 7 }v[maxn];
 8 int main()
 9 {
10     int n,m,op;
11     scanf("%d",&n);
12     while(n--)
13     {
14         scanf("%d",&op);
15         v[op].pre1=1;
16     }
17     scanf("%d",&m);
18     while(m--)
19     {
20         scanf("%d",&op);
21         v[op].pre2=1;
22     }
23     int ans=0,flag=3;
24     for(int i=0;i<maxn;i++)
25     {
26         if(v[i].pre1==1&&v[i].pre2==1)
27         {
28             ans++;
29             flag=3;
30         }
31         else if(v[i].pre1==1&&v[i].pre2==0)
32         {
33             if(flag==2||flag==3)
34             {
35                 ans++;
36                 flag=1;
37             }
38         }
39         else if(v[i].pre1==0&&v[i].pre2==1)
40         {
41             if(flag==1||flag==3)
42             {
43                 ans++;
44                 flag=2;
45             }
46         }
47     }
48     printf("%d\n",ans);
49     return 0;
50 }
View Code

 

转载于:https://www.cnblogs.com/scott527407973/p/9532986.html

这篇关于UPC2018组队训练赛第三场的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:https://blog.csdn.net/weixin_30764883/article/details/98455861
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/335901

相关文章

CPC23第三场、第四场总结

这两天跟着Arthur学长们混了两天现场赛,有种打怪升级的感觉,就是90级的老大们带30级的我去打100级的BOSS,看着Arthur他们在不断的输出,我在一旁水经验·······不过我也没闲着玩泥巴,在status里留下了一大片WA、TLE、RE··········         CPC23第三场,开场19分钟,Arthur全场一A了C题,于是我就开始跟着切C题。看了一眼题目

2015多校联合训练第三场Work(hdu5326)

题意: a是b的上司,b是c的上司,则a是c的上司,问构成一个树种,有多人是 k个人的上司 思路: 先找出root,然后dfs一下就行 #include <bits/stdc++.h>#define LL long longusing namespace std;const int MAXN = 1e6;int f[105];int n, k;int mp[101][101];

2015年多校联合训练第三场RGCDQ(hdu5317)

题意: f(i)代表i数中有的素数的种数,给出区间[l,r],求区间内max(gcd(f(i))), 由于i最大是1e6,2*3*5*7*11*13*17>1e6,故最多不超过7种素数, 先打表打出1e6内的素数种数表,然后用sum[i][j]代表1-i个数中,还有j个素数的个数,最后用sum[r][j] - sum[l-1][j]求出区间内含有j个素数的数的个数,暴力找出1,2,3,4,5

训练赛3

http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=2348&cid=1232 题意: 有两个磁盘,第一个磁盘有n个安装包,第二个磁盘有m个安装包。有些安装包的安装依赖于其他安装包的安装,即如果x依赖与y,那么包y必须在包x之前安装,每次可以插入这两张磁盘中的一张去安装一些包,求以最小的交换次数安装好所有的包,保证依赖关系不存在环,开始插入和最

训练赛 Grouping(强连通分量缩点 + DAG求最长路)

http://acm.sdut.edu.cn:8080/vjudge/contest/view.action?cid=158#problem/F 大致题意:给出n个人和m种关系(ti,si),表示ti的年龄不小于si。问最小能被划分为几个集合,每个集合都要满足里面的人都无法比较。 思路:对于一条路上的点,它们必定不能被划分到同一个集合中,因此原题变为求一条最长路。而题目中有可能出现

网络赛 (初次组队赛)

四个人一个队有没有见过 其实感觉没啥区别    总结了好几点 第一  不知道怎莫组队   第二  不知道怎么分配题目

hdu5289 Assignment --2015多校训练赛(一)

题意: 给定一串数字,里面存在多少个区间[l, r] 使得里面的最大值与最小值之差小于k。 思路: 用RMQ预处理出所有区间的最大值与最小值之差。之后枚举左端点L, 二分处理差值小于k的最左边端点R,把所有 的R-L+1加上就是答案。 /************************************************ Author: fisty* Create

AI圈-数据结构与算法面试组队刷题活动

原文转自:https://mp.weixin.qq.com/s/43AWhN90SSskeFf0ZGFIug 笔者面试准备之余写了篇小结:面试必刷-《剑指offer》刷题小结 我们组建了一个面试刷题讨论组,目前已经有不少小伙伴了。考虑到自身和大家的共同需求,欢迎有面试需求和算法刷题爱好者加入一起刷题。 内容: 优先推荐刷剑指offer与leetcode。 规则: 缴纳19.9保证金,5

【2024最新华为OD-C/D卷试题汇总】[支持在线评测] 部门组队编程(200分) - 三语言AC题解(Python/Java/Cpp)

🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员 ✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解 💻 ACM银牌🥈| 多次AK大厂笔试 | 编程一对一辅导 👏 感谢大家的订阅➕ 和 喜欢💗 📎在线评测链接 https://app5938.acapp.acwing.com.cn/contest/2/problem/OD1060 🌍 评测功能需要 ⇒ 订阅专栏 ⇐

有关组队以及自主学习的一些感想

本来是上周末就打算写一篇东西来纪念一下我们团队第一次合作的。但是由于成品一直没做好,整个人一直在做那个界面所以也就没来的及写。        因为那天龙哥讲了一些界面,这让我产生了很大的兴趣,然后就开始写了。虽然有的人觉得功能比较重要,但是我个人觉得一个好的界面,也是一个项目的关键,现在不是都提倡用户友好么~        一开始做出来的,像拼图一样的东西。 当时的构想是点开每个