第九届西电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;
    }
}

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个队，也可以直接扫一遍，这样可以简化不少代码。每一次调度都相当于删掉老的人再在队尾加入一个新的人，其中对于删除操作用一个双端链表来模拟队列会比较简单，如果用普通的队列则用标记的方法，但要处理很多细节。
另外一个关键点是操作的处理顺序，这需要很仔细地看题意。"

第九届西电ACM校赛解答

热门文章

最新文章

相关课程

相关电子书

相关实验场景