第九届西电ACM校赛解答

2019-04-13 13:51发布

站内文章 / 模拟电子
17851 0 937
Description 欢迎参加西电第九届ACM校内赛！作为一名经历了四届校赛的ACM老队员以及本次校赛的出题人，每次校赛都让我有一种全新的感受——有第一次参加校赛时提交代码时紧张到双手发抖，也有当裁判时看到有些不明真相的人提交编译后程序时的欢乐。不管你是第几次参赛，好好享受这一刻带给你的各种感受，经历就是一种财富。为了让大家更好地记住这悲喜交加的日子，特意准备了这么一道题：
给你一个日期，你只要输出这个日期是在校赛前还是校赛后，或者刚好就是校赛那一天（2011年5月22号）。
题目是什么意思呢？Good luck and have fun，祝大家在本次校赛取得好成绩！ Input 输入数据的第一行是一个正整数T（0 每组测试数据只有一行，为三个数字Y,M,D（0 2000 2 29
2011 5 22
2011 11 11
Sample Output before
nice day
after
Hint Source qinz #include #include using namespace std; int a,b,c,t; int main() { cin>>t; while (t--) { cin>>a>>b>>c; if (a==2011 && b==5 && c==22) {cout<<"nice day"< PB Description 统一资源定位符也被称为网页地址，是因特网上标准的资源的地址（Address)。它最初是由蒂姆·伯纳斯-李发明用来作为万维网的地址的。现在它已经被万维网联盟编制为因特网标准RFC1738了。

因特网上的可用资源可以用简单字符串来表示，被称为“统一资源定位器”（URL，Uniform / Universal Resource Locator）。URL是一种标准化的命名方法，它可以用统一的格式来表示Internet提供的各种服务中信息资源的地址，以便在浏览器中使用相应的服务。

统一资源定位符的标准格式如下：
协议类型://服务器地址(:端口号)/路径/文件名

在应用中，我们常常需要从一条URL中截取远程服务器地址部分（IP地址或域名），以便进一步处理。为此我们提出了一个新算法来实现该功能，基于……

呃，写到这里卡住了，现在需要你来实现这个“新算法”，输出所给URL中的远程服务器地址部分。 Input 输入数据的第一行是一个正整数T（0 每组测试数据只有一行，包含一条URL（长度小于1000个字符，为可见ASCII字符），其中不包含空格，符合URL标准格式。 Output 对于每组测试数据，在一行上输出该URL地址中的远程服务器地址部分（IP地址或域名，不包含端口号）。 Sample Input 5
http://acm.xidian.edu.cn/
http://qinz.maybe.im/
https://www.something.com:8080/p?id=0
ftp://ftp.anything.com/nothing.zip
http://127.0.0.1/a/b/c/d/e Sample Output acm.xidian.edu.cn
qinz.maybe.im
www.something.com
ftp.anything.com
127.0.0.1
Hint Source qinz   浅析统一资源定位符中的远程服务器地址检测 简单 题意好长，实际意思就是提取一个url地址的IP地址或域名部分，即第二个/与下一个:或/之间的内容。
懒人可以试下scanf(“%*[^/]//%[^/:]%*s”,c);puts(c); #include #include #include using namespace std; int main(){ ifstream in("E:\read.txt"); string s; int t=0,j,start; int i=0; while(getline(in,s)){ //cout<pc

Description

经历了时间的洗礼，ZYF已经比去年成熟多了，最喜欢的活动不再是走楼梯，而是打麻将！作为一个有深度的人，他不满足于每人只有十几张牌的普通麻将。经过一段时间潜心研究，他发明出一种只有一种花 {MOD}、每人几十张甚至上百张牌的高级麻将。

这也导致了他一时难以知道听牌时到底需要哪些牌，现在他需要你的帮忙。给你当前的牌局，请计算出他听了哪几门。

以下是这种高级麻将的一些资料：1. 只有一种花 {MOD}，有M种牌，分别是1,2,3...M，每种牌最多只有四张牌。2. 两张一样的牌称为对子，如（2,2）；三张一样的牌称为刻子，如（5,5,5）；三张数字连续的牌称为顺子，如（6,7,8），其它组合不考虑。3. 为了让问题简单化，胡牌时必须有且仅有一个对子，剩下的全是刻子或顺子。如（2,2,5,5,5,6,6,6,7,8,9）。4. 听牌是指再多一张合适的牌即可胡牌，可能有多张不同且合适的牌，即听多门。如（3,4,5,5）听2或5，（8）听8，（6,6,7,7）听6或7。

Input
输入数据的第一行是一个正整数T（0
Output
对于每组测试数据，输出一行整数，其中，第一个正整数表示听的门数Q，接下来为Q个正整数，表示听的牌的数值Pi，整数之间以一个空格隔开。
Sample Input
513 91 1 3 3 3 5 5 5 7 7 7 9 913 91 3 3 3 5 5 5 7 7 7 7 8 91 200102 105 55 109 7 5 3 1
Sample Output
2 1 92 1 21 1000
Hint
Source
qinz
#include
#include #include using namespace std; int vis[205]; int sum; int n,m; int arr[205],brr[205]; int a,b,c,d,e,f; void cop() { int a; for (a=1;a<=m;a++) brr[a]=arr[a]; } int main() { int t; cin>>t; while (t--) { cin>>n>>m; sum=0; memset(arr,0,sizeof(arr)); memset(brr,0,sizeof(brr)); memset(vis,0,sizeof(vis)); for (a=1;a<=n;a++) {cin>>b; arr[b]++;} for (a=1;a<=m;a++) { if (arr[a]<4) { arr[a]++; for (b=1;b<=m;b++) if (vis[a]==0 && arr[b]>=2) { cop(); //for (d=1;d<=m;d++) if (brr[d]!=0) cout<=3) brr[c]-=3; while (brr[c]>=1 && brr[c+1]>=1 && brr[c+2]>=1) { brr[c]--; brr[c+1]--; brr[c+2]--; } if (brr[c]!=0) break; } if (c==m+1) {sum++; vis[a]=1;} } arr[a]--; } } cout<
PD; Description “自然科学的皇后是数学。数学的皇冠是数论。哥德巴赫猜想，则是皇冠上的明珠。”哥德巴赫猜想表述为：任一大于2的偶数都可写成两个质数之和。当然我们今天不是来证明哥德巴赫猜想的，而是验证对于比较小的偶数其猜想是否成立。 Input 数据的第一行是一个正整数T（0 每组测试数据只有一行，为一个偶数M（2 6
10
12 Sample Output 3 3
5 5
5 7
Hint Source qinz
#include //#include #include int is_z(int x) { int i=1; if(x==2) return 1; else while(++i<=(int)sqrt(x)+1) {if(x%i==0) return 0;} return 1; } //int z[60000];//zhu shu biao int main() { int i,j=0,t,m,k,s,min,mini=0,mink=0; //for(i=2;i<60000;i++) // if(is_z(i)) z[j++]=i; scanf("%d",&t); while(t--&&scanf("%d",&m)==1) { mini=m/2; mink=m/2; if(m%2==0) while(1) { if(is_z(mini)&&is_z(mink)) {printf("%d %d ",mini,mink);break;} mini--; mink++; } //printf("%d %d ",mini,mink); } return 0; } Description 作为一个实验室，单单只有计算机显得很不专业，为此WM也经常在实验室做一些物理、化学、生物、社会实验。一次他想通过把一些化合物混合在一起来制成炸药，而这些化合物的每种都有一个“特征值”Ai，如果混合物中有两种化合物“特征值”差的绝对值大于某个阀值M，则将它们混在一起会相当不稳定，随时可能爆炸——显然这种炸药是没前途的。另一方面，他想使他的炸药爆炸起来威力大点，在此我们简单地假设混合物中包含的化合物越多威力越大。现在实验室有N种不同的化合物，WM最多能把几种不同的化合物混在一起、形成一种有前途的炸药呢？ Input 输入数据的第一行是一个正整数T（0 每组测试数据有两行：
第一行为两个整数N,M（0 第二行包含N个整数，代表N种化合物的“特征值”Ai（0 3 2
1 3 5
3 1
1 3 5
5 2
3 5 3 4 1
Sample Output 2
1
4
Hint Source qinz #include
#include
#include
#include
using namespace std;
int arr[105000];
int n,m;
int head,tail;
int best;
int i,j,l,r,a;
int t;
int main()
{
    cin>>t;
    while (t--)
    {
          best=1;
          cin>>n>>m;
          for (a=0;ascanf("%d",&arr[a]);
          sort(arr,arr+n);
          head=0; tail=0;
          while (head
          {
                while (tail+1
                //cout<                best=max(best,tail-head+1);
                head++;
          }
          cout<
    }
}
Description SHF是一个很神奇的人，他的电脑也采用了一种奇怪的密码验证方式，即一串数字的某个排列。CX是一个密码破解爱好者，当然对于这种密码很有兴趣。现在他知道SHF的初始密码是(1,2,3,...,N)，每次用两个数字A和B来修改密码，也就是把[A,B]位置区间的数字反序，包括A、B位置的数字（A,B以1作为起始编号）。例如，现在的密码是(2,1,3,5,4)，密码修改操作的数字是2和5，则修改后的密码为(2,4,5,3,1)。CX已经知道了SHF所有的密码修改操作的序列，但由于操作次数实在太多了，他计算不出最后的密码是什么，现在他需要你帮他计算出最后的密码。 Input 输入数据的第一行是一个正整数T（0 每组测试数据的第一行包含两个整数N,M（0 接下来有M行，每行有两个整数A,B（0 5 2
1 3
4 5
5 2
1 4
2 5 Sample Output 3 2 1 5 4
4 5 1 2 3 Hint Source qinz
#include #include #include using namespace std; int arr[105000]; int n,m; int i,j,l,r,a; int t; int main() { cin>>t; while (t--) { cin>>n>>m; for (a=1;a<=n;a++) arr[a]=a; for (a=1;a<=m;a++) { scanf("%d%d",&l,&r); while (l Description 排队是文明的表现，排好队则需要一些智慧。TripleZ队员提出了Z排队调度算法（Zlgorithm）——但似乎不怎么靠谱，不过可以试试看。

假设有N个人M个队列（人和队列都是从0开始编号，队列可以为空），第i个人在Pi时刻加入了Qi号队列，排到队头后需要花Ai时间来处理任务，而Zlgorithm需要做的是把某个人从一个队列拉出来，将其排到某个队列的尾部。

现在给出每个人开始排队的详细情况，以及给出Zlgorithm的调度指令，要求输出用Zlgorithm算法调度后的平均排队时间。对于任意一个时刻，如果有多个动作，则先按人的编号顺序进行出队处理，然后按人的编号顺序进行入队处理，最后按人的编号顺序处理调度指令。如果一个人正在处理任务时被调走，再次排到他的时候需要从头开始处理任务。
  Input 输入数据的第一行是一个正整数T（0 每组测试数据的第一行为N,M,C（0 接下来是N行，每行包括Pi,Qi,Ai（0<=Pi<=10^9, 0<=Qi 接下来是C行，每行包含Zi,Bi,QTi（0<=Zi<=10^9, 0<=Bi 3 2 1
0 0 4
1 1 5
3 1 2
4 2 0
5 5 2
0 0 10
2 0 11
1 0 12
5 0 13
4 0 14
8 3 1
7 4 2 Sample Output 4.00
19.00 Hint Source qinz
她说："E又是难题，全场没有一个通过。写到这里才发现今年的题目难度分布跟去年基本是一样的，意外。 西电校赛少有的模拟题。本来打算出的题数据范围是比这个要大，而且规则也要复杂点，但考虑到校赛时间不长，而且自己也不是很喜欢这种题，最后还是简化了一下。
直接用队列来模拟，对于每个队列的队头可以放到一个优先队列来判断哪个先排完——当然这题的数据范围比较小，只有100个队，也可以直接扫一遍，这样可以简化不少代码。每一次调度都相当于删掉老的人再在队尾加入一个新的人，其中对于删除操作用一个双端链表来模拟队列会比较简单，如果用普通的队列则用标记的方法，但要处理很多细节。
另外一个关键点是操作的处理顺序，这需要很仔细地看题意。"

热门文章