第九届西电ACM校赛解答

简介: Description 欢迎参加西电第九届ACM校内赛!作为一名经历了四届校赛的ACM老队员以及本次校赛的出题人,每次校赛都让我有一种全新的感受——有第一次参加校赛时提交代码时紧张到双手发抖,也有当裁判时看到有些不明真相的人提交编译后程序时的欢乐。
Description

欢迎参加西电第九届ACM校内赛!作为一名经历了四届校赛的ACM老队员以及本次校赛的出题人,每次校赛都让我有一种全新的感受——有第一次参加校赛时提交代码时紧张到双手发抖,也有当裁判时看到有些不明真相的人提交编译后程序时的欢乐。不管你是第几次参赛,好好享受这一刻带给你的各种感受,经历就是一种财富。为了让大家更好地记住这悲喜交加的日子,特意准备了这么一道题:
给你一个日期,你只要输出这个日期是在校赛前还是校赛后,或者刚好就是校赛那一天(2011年5月22号)。
题目是什么意思呢?Good luck and have fun,祝大家在本次校赛取得好成绩!

Input
输入数据的第一行是一个正整数T(0<T<=100),表示有T组测试数据。
每组测试数据只有一行,为三个数字Y,M,D(0<Y<=10000, 0<M<=12, 0<D<=31),表示Y年M月D号。日期符合现实日期规范。
Output
对于每组测试数据,在一行上输出一个字符串:如果在校赛日前之前,则输出"before";如果在校赛日期之后,则输出"after";如果刚好是校赛那天,则输出"nice day"。
Sample Input
3
2000 2 29
2011 5 22
2011 11 11
Sample Output
before
nice day
after
Hint
Source
qinz

#include<iostream>
#include<string.h>
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"<<endl;continue;}
          if (a<2011) {cout<<"before"<<endl;continue;}
          if (a==2011 && b<5) {cout<<"before"<<endl;continue;}
          if (a==2011 && b==5 && c<22) {cout<<"before"<<endl;continue;}
          cout<<"after"<<endl;
    }
}

PB

Description

统一资源定位符也被称为网页地址,是因特网上标准的资源的地址(Address)。它最初是由蒂姆·伯纳斯-李发明用来作为万维网的地址的。现在它已经被万维网联盟编制为因特网标准RFC1738了。

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

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

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

呃,写到这里卡住了,现在需要你来实现这个“新算法”,输出所给URL中的远程服务器地址部分。

Input
输入数据的第一行是一个正整数T(0<T<=100),表示有T组测试数据。
每组测试数据只有一行,包含一条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<string>
#include<iostream>
#include<fstream>
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<<s<<endl;
	   // t++;
		for(j=0;j<s.length();j++)
        {
            if(s[j]=='/' && s[j+1]=='/')
            {
                break;
            }
        }
        start=j+2;
        for(j=start;j<s.length();j++)
        {
            if(s[j]==':' || s[j]=='/')
                break;
            cout<<s[j];
        }
        cout<<endl;
	}
    return 0;
}
</pre>pc<p></p><div class="ptt" style="font-size:14px; line-height:30px; width:940px; margin:10px 20px 0px 25px; padding-left:10px; font-weight:bold; font-family:Verdana; background-color:rgb(231,240,255)">Description</div><div class="ptx" style="line-height:18px; width:930px; margin:0px 30px 10px 25px; padding:5px 0px 5px 20px; word-wrap:break-word; font-family:Verdana; background-color:rgb(247,255,231)"><p>经历了时间的洗礼,ZYF已经比去年成熟多了,最喜欢的活动不再是走楼梯,而是打麻将!作为一个有深度的人,他不满足于每人只有十几张牌的普通麻将。经过一段时间潜心研究,他发明出一种只有一种花色、每人几十张甚至上百张牌的高级麻将。</p><p>这也导致了他一时难以知道听牌时到底需要哪些牌,现在他需要你的帮忙。给你当前的牌局,请计算出他听了哪几门。</p><p>以下是这种高级麻将的一些资料:1. 只有一种花色,有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。</p></div><div class="ptt" style="font-size:14px; line-height:30px; width:940px; margin:10px 20px 0px 25px; padding-left:10px; font-weight:bold; font-family:Verdana; background-color:rgb(231,240,255)">Input</div><div class="ptx" style="line-height:18px; width:930px; margin:0px 30px 10px 25px; padding:5px 0px 5px 20px; word-wrap:break-word; font-family:Verdana; background-color:rgb(247,255,231)">输入数据的第一行是一个正整数T(0<T<=10),表示有T组测试数据。每组测试数据有两行:第一行有两个正整数N,M(0<N,M<=200),表示当前有N张牌,该局麻将有M种牌。第二行有N个正整数,以空格隔开,表示当前N张牌的整数Ai(0<Ai<=M)。</div><div class="ptt" style="font-size:14px; line-height:30px; width:940px; margin:10px 20px 0px 25px; padding-left:10px; font-weight:bold; font-family:Verdana; background-color:rgb(231,240,255)">Output</div><div class="ptx" style="line-height:18px; width:930px; margin:0px 30px 10px 25px; padding:5px 0px 5px 20px; word-wrap:break-word; font-family:Verdana; background-color:rgb(247,255,231)">对于每组测试数据,输出一行整数,其中,第一个正整数表示听的门数Q,接下来为Q个正整数,表示听的牌的数值Pi,整数之间以一个空格隔开。</div><div class="ptt" style="font-size:14px; line-height:30px; width:940px; margin:10px 20px 0px 25px; padding-left:10px; font-weight:bold; font-family:Verdana; background-color:rgb(231,240,255)">Sample Input</div><div class="ptx" style="line-height:18px; width:930px; margin:0px 30px 10px 25px; padding:5px 0px 5px 20px; word-wrap:break-word; font-family:Verdana; background-color:rgb(247,255,231)">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</div><div class="ptt" style="font-size:14px; line-height:30px; width:940px; margin:10px 20px 0px 25px; padding-left:10px; font-weight:bold; font-family:Verdana; background-color:rgb(231,240,255)">Sample Output</div><div class="ptx" style="line-height:18px; width:930px; margin:0px 30px 10px 25px; padding:5px 0px 5px 20px; word-wrap:break-word; font-family:Verdana; background-color:rgb(247,255,231)">2 1 92 1 21 1000</div><div class="ptt" style="font-size:14px; line-height:30px; width:940px; margin:10px 20px 0px 25px; padding-left:10px; font-weight:bold; font-family:Verdana; background-color:rgb(231,240,255)">Hint</div><div class="ptx" style="line-height:18px; width:930px; margin:0px 30px 10px 25px; padding:5px 0px 5px 20px; word-wrap:break-word; font-family:Verdana; background-color:rgb(247,255,231)"></div><div class="ptt" style="font-size:14px; line-height:30px; width:940px; margin:10px 20px 0px 25px; padding-left:10px; font-weight:bold; font-family:Verdana; background-color:rgb(231,240,255)">Source</div><div class="ptx" style="line-height:18px; width:930px; margin:0px 30px 10px 25px; padding:5px 0px 5px 20px; word-wrap:break-word; font-family:Verdana; background-color:rgb(247,255,231)">qinz</div><pre name="code" class="cpp"><span style="font-family: Arial, Helvetica, sans-serif;">#include<iostream></span>
#include<string.h>
#include<stdio.h>
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<<d<<' '<<brr[d]<<endl;
                    brr[b]-=2;
                    for (c=1;c<=m;c++)
                    {
                        if (brr[c]==0) continue;
                        if (brr[c]>=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<<sum;
        for (a=1;a<=m;a++) if (vis[a]==1) cout<<" "<<a;
        cout<<endl;
    }
}   

PD;

Description

“自然科学的皇后是数学。数学的皇冠是数论。哥德巴赫猜想,则是皇冠上的明珠。”哥德巴赫猜想表述为:任一大于2的偶数都可写成两个质数之和。当然我们今天不是来证明哥德巴赫猜想的,而是验证对于比较小的偶数其猜想是否成立。

Input
数据的第一行是一个正整数T(0<T<=100),表示有T组测试数据。
每组测试数据只有一行,为一个偶数M(2<M<=100000),表示要验证的偶数。
Output
对于每组测试数据,在一行上输出两个质数A,B(A<=B),表示M=A+B,如果有多种可能,则输出B-A的值最小的那组。
Sample Input
3
6
10
12
Sample Output
3 3
5 5
5 7
Hint
Source
qinz

#include <stdio.h>
//#include <stdlib.h>
#include <math.h>
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\n",mini,mink);break;}
            mini--;
            mink++;
        }
        //printf("%d %d\n",mini,mink);
    }
    return 0;
}

Description

作为一个实验室,单单只有计算机显得很不专业,为此WM也经常在实验室做一些物理、化学、生物、社会实验。一次他想通过把一些化合物混合在一起来制成炸药,而这些化合物的每种都有一个“特征值”Ai,如果混合物中有两种化合物“特征值”差的绝对值大于某个阀值M,则将它们混在一起会相当不稳定,随时可能爆炸——显然这种炸药是没前途的。另一方面,他想使他的炸药爆炸起来威力大点,在此我们简单地假设混合物中包含的化合物越多威力越大。现在实验室有N种不同的化合物,WM最多能把几种不同的化合物混在一起、形成一种有前途的炸药呢?

Input
输入数据的第一行是一个正整数T(0<T<=100),表示有T组测试数据。
每组测试数据有两行:
第一行为两个整数N,M(0<N<=100000, 0<M<=10^9),表示有N种不同的化合物,爆炸阀值为M。
第二行包含N个整数,代表N种化合物的“特征值”Ai(0<Ai<=10^9)。
Output
对于每组测试数据,在一行上输出一个整数P,表示最多能把P种化合物混合在一起。
Sample Input
3
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<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
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;a<n;a++)  scanf ( "%d" ,&arr[a]);
          sort(arr,arr+n);
          head=0; tail=0;
           while  (head<n)
          {
                 while  (tail+1<n && arr[tail+1]-arr[head]<=m) tail++;
                 //cout<<head<<' '<<tail<<endl;
                best=max(best,tail-head+1);
                head++;
          }
          cout<<best<<endl;
    }
}
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<T<=10),表示有T组测试数据。
每组测试数据的第一行包含两个整数N,M(0<N<=100000, 0<=M<=2000),表示初始密码为(1,2,3,...,N),共有M次密码修改操作。
接下来有M行,每行有两个整数A,B(0<A<=B<=N),表示进行一次密码修改操作,意义如上所述。
Output
对于每组测试数据,在一行上输出N个整数,表示最后的密码。整数之间以一个空格隔开。
Sample Input
2
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<iostream>
#include<string.h>
#include<stdio.h>
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<r)
              {
                    swap(arr[l],arr[r]);
                    l++; r--;
              }
          }
          for (a=1;a<=n;a++)
          {
              if (a!=1) printf(" ");
              printf("%d",arr[a]);
          }
          cout<<endl;
    }
}

Description

排队是文明的表现,排好队则需要一些智慧。TripleZ队员提出了Z排队调度算法(Zlgorithm)——但似乎不怎么靠谱,不过可以试试看。

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

现在给出每个人开始排队的详细情况,以及给出Zlgorithm的调度指令,要求输出用Zlgorithm算法调度后的平均排队时间。对于任意一个时刻,如果有多个动作,则先按人的编号顺序进行出队处理,然后按人的编号顺序进行入队处理,最后按人的编号顺序处理调度指令。如果一个人正在处理任务时被调走,再次排到他的时候需要从头开始处理任务。
 

Input
输入数据的第一行是一个正整数T(0<T<=10),表示有T组测试数据。
每组测试数据的第一行为N,M,C(0<N<=10000, 0<M=<100, 0<=C<=100)三个整数,表示N个人、M个队列、C条Zlgorithm调度指令。
接下来是N行,每行包括Pi,Qi,Ai(0<=Pi<=10^9, 0<=Qi<M, 0<Ai<=100),意义如上所述。
接下来是C行,每行包含Zi,Bi,QTi(0<=Zi<=10^9, 0<=Bi<N, 0<=QTi<M),表示Zi时刻把编号为Bi的人调到QTi队尾,如果Zi时刻Bi不在队列中则忽略本次调度。
Output
对于每组数据,在一行上输出一个实数(保留两位小数),表示平均排队时间。
Sample Input
2
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个队,也可以直接扫一遍,这样可以简化不少代码。每一次调度都相当于删掉老的人再在队尾加入一个新的人,其中对于删除操作用一个双端链表来模拟队列会比较简单,如果用普通的队列则用标记的方法,但要处理很多细节。
另外一个关键点是操作的处理顺序,这需要很仔细地看题意。"

目录
相关文章
集美大学第九届程序设计竞赛
集美大学第九届程序设计竞赛
69 0
|
定位技术 Go
第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(银川),签到题5题
第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(银川),签到题5题
96 0
|
7月前
|
机器学习/深度学习 人工智能
第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(昆明),签到题4题
第 45 届国际大学生程序设计竞赛(ICPC)亚洲区域赛(昆明),签到题4题
76 0
桂林电子科技大学第三届ACM程序设计竞赛 C题
桂林电子科技大学第三届ACM程序设计竞赛 C题
134 0
桂林电子科技大学第三届ACM程序设计竞赛 D题
桂林电子科技大学第三届ACM程序设计竞赛 D题
104 0
桂林电子科技大学第三届ACM程序设计竞赛 I题
桂林电子科技大学第三届ACM程序设计竞赛 I题
82 0
桂林电子科技大学第三届ACM程序设计竞赛 F题
桂林电子科技大学第三届ACM程序设计竞赛 F题
87 0
桂林电子科技大学第三届ACM程序设计竞赛 E题
桂林电子科技大学第三届ACM程序设计竞赛 E题
74 0
桂林电子科技大学第三届ACM程序设计竞赛 J题
桂林电子科技大学第三届ACM程序设计竞赛 J题
89 0
桂林电子科技大学第三届ACM程序设计竞赛 H题
桂林电子科技大学第三届ACM程序设计竞赛 H题
76 0
下一篇
无影云桌面