1．數字反轉 reverse
【問題描述】
給定一個整數，請將該數各個位上數字反轉得到一個新數。新數也應滿足整數的常見形式，即除非給定的原數爲零，否則反轉後得到的新數的最高位數字不應爲零（參見樣例2）。
【輸入】
輸入文件名爲reverse.in。
輸入共1 行，一個整數N。
【輸出】
輸出文件名爲reverse.out。
輸出共1 行，一個整數，表示反轉後的新數。
【輸入輸出樣例1】
reverse.in
123
reverse.out
321
【輸入輸出樣例2】
reverse.in
-380
reverse.out
-83
【數據範圍】
-1,000,000,000 ≤ N≤ 1,000,000,000。
【分析】
普及組的水題，直接模擬即可。
注意：
1.讀入時用字符串讀入。
2.注意輸入“0”的情況。
【我的代碼】
C++语言: Codee#24218
//NOIP2011_Junior_reverse
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
freopen("reverse.in","r",stdin);
freopen("reverse.out","w",stdout);
char line[100]={'\0'};
scanf("%s\n",&line);
int s=0;
int len=strlen(line);
len--;
if(line[0]=='0')
printf("0\n");
else
{
if(line[0]=='-')
{
s++;
printf("-");
}
while(line[len--]=='0');
for (int i=len+1;i>=s;i--)
printf("%c",line[i]);
printf("\n");
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main()
{
freopen("reverse.in","r",stdin);
freopen("reverse.out","w",stdout);
char line[100]={'\0'};
scanf("%s\n",&line);
int s=0;
int len=strlen(line);
len--;
if(line[0]=='0')
printf("0\n");
else
{
if(line[0]=='-')
{
s++;
printf("-");
}
while(line[len--]=='0');
for (int i=len+1;i>=s;i--)
printf("%c",line[i]);
printf("\n");
}
return 0;
}
【評測結果】
正在连接评测机...
已连接到评测机
| GRID | 1 |
| 名称 | Flitty |
| 系统版本 | 1.00 |
| 备注 | COGS 1号评测机 Flitty |
编译成功
| 测试点 | 结果 | 得分 | 运行时间 | 内存使用 | 退出代码 |
| 1 | 正确 | 10 | 0.000 s | 273 KB | 0 |
| 2 | 正确 | 10 | 0.000 s | 273 KB | 0 |
| 3 | 正确 | 10 | 0.000 s | 273 KB | 0 |
| 4 | 正确 | 10 | 0.000 s | 273 KB | 0 |
| 5 | 正确 | 10 | 0.000 s | 273 KB | 0 |
| 6 | 正确 | 10 | 0.000 s | 273 KB | 0 |
| 7 | 正确 | 10 | 0.000 s | 273 KB | 0 |
| 8 | 正确 | 10 | 0.000 s | 273 KB | 0 |
| 9 | 正确 | 10 | 0.000 s | 273 KB | 0 |
| 10 | 正确 | 10 | 0.000 s | 273 KB | 0 |
运行时间 0.003 s
平均内存使用 273 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!
2.統計單詞數 stat
【問題描述】
一般的文本編輯器都有查找單詞的功能，該功能可以快速定位特定單詞在文章中的位置，有的還能統計出特定單詞在文章中出現的次數。
現在，請你編程實現這一功能，具體要求是：給定一個單詞，請你輸出它在給定的文章中出現的次數和第一次出現的位置。注意：匹配單詞時，不區分大小寫，但要求完全匹配，即給定單詞必須與文章中的某一獨立單詞在不區分大小寫的情況下完全相同（參見樣例1），如果給定單詞僅是文章中某一單詞的一部分則不算匹配（參見樣例2）。
【輸入】
輸入文件名爲stat.in，2 行。
第1 行爲一個字符串，其中只含字母，表示給定單詞；
第2 行爲一個字符串，其中只可能包含字母和空格，表示給定的文章。
【輸出】
輸出文件名爲stat.out。
只有一行，如果在文章中找到給定單詞則輸出兩個整數，兩個整數之間用一個空格隔開，分別是單詞在文章中出現的次數和第一次出現的位置（即在文章中第一次出現時，單詞首字母在文章中的位置，位置從0 開始）；如果單詞在文章中沒有出現，則直接輸出一個整數-1。
【輸入輸出樣例1】
stat.in
To
to be or not to be is a question
stat.out
2 0
【輸入輸出樣例1 說明】
輸出結果表示給定的單詞To 在文章中出現兩次，第一次出現的位置爲0。
【輸入輸出樣例2】
stat.in
to
Did the Ottoman Empire lose its power at that time
stat.out
-1
【輸入輸出樣例2 說明】
表示給定的單詞to 在文章中沒有出現，輸出整數-1。
【數據範圍】
1 ≤ 單詞長度≤ 10。
1 ≤ 文章長度≤ 1,000,000。
【分析】這是NOIP2011複賽普及組中的第二道字符串處理題了～
讀入時都把大寫字母轉換成小寫，以方便判斷。
然後就很簡單了，直接暴力枚舉即可。
如果是string類，則之間用“=”號判等；如果是char型數組，用strcmp函數判等。
注意：
1.文章中空格有可能不止1個，要加以判斷。
2.只有strcmp函數返回0時才表示兩個字符數組相等。
【我的代碼】
C++语言: Codee#24217
//NOIP2011_Junior_stat
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
int main()
{
freopen("stat.in","r",stdin);
freopen("stat.out","w",stdout);
char str[11];
memset(str,'\0',sizeof(str));
int len;
cin>>str;
len=strlen(str);
for (int i=0;i<len;i++)
str[i]=tolower(str[i]);
string art;
char tmp[1000001]={'\0'};
int pos=-1;
int tot=0;
int tl;
getline(cin,art);
getline(cin,art);
tl=art.length();
for (int i=0;i<tl;i++)
tmp[i]=art[i];
int i=0;
while(i<tl)
{
if(isalpha(tmp[i]))
{
int j=i;
int k=0;
char arr[1001]={'\0'};
while(isalpha(tmp[j]))
{
arr[k]=tolower(tmp[j]);
k++;
j++;
}
if(strcmp(str,arr)==0)
{
tot++;
if(pos==-1)
pos=i;
}
i=j+1;
}
else
i++;
}
if(tot!=0)
cout<<tot<<" "<<pos<<endl;
else
cout<<-1<<endl;
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
int main()
{
freopen("stat.in","r",stdin);
freopen("stat.out","w",stdout);
char str[11];
memset(str,'\0',sizeof(str));
int len;
cin>>str;
len=strlen(str);
for (int i=0;i<len;i++)
str[i]=tolower(str[i]);
string art;
char tmp[1000001]={'\0'};
int pos=-1;
int tot=0;
int tl;
getline(cin,art);
getline(cin,art);
tl=art.length();
for (int i=0;i<tl;i++)
tmp[i]=art[i];
int i=0;
while(i<tl)
{
if(isalpha(tmp[i]))
{
int j=i;
int k=0;
char arr[1001]={'\0'};
while(isalpha(tmp[j]))
{
arr[k]=tolower(tmp[j]);
k++;
j++;
}
if(strcmp(str,arr)==0)
{
tot++;
if(pos==-1)
pos=i;
}
i=j+1;
}
else
i++;
}
if(tot!=0)
cout<<tot<<" "<<pos<<endl;
else
cout<<-1<<endl;
return 0;
}
【評測結果】
正在连接评测机...
已连接到评测机
| GRID | 1 |
| 名称 | Flitty |
| 系统版本 | 1.00 |
| 备注 | COGS 1号评测机 Flitty |
编译成功
| 测试点 | 结果 | 得分 | 运行时间 | 内存使用 | 退出代码 |
| 1 | 正确 | 10 | 0.001 s | 1172 KB | 0 |
| 2 | 正确 | 10 | 0.001 s | 1172 KB | 0 |
| 3 | 正确 | 10 | 0.001 s | 1172 KB | 0 |
| 4 | 正确 | 10 | 0.001 s | 1168 KB | 0 |
| 5 | 正确 | 10 | 0.003 s | 1168 KB | 0 |
| 6 | 正确 | 10 | 0.018 s | 1176 KB | 0 |
| 7 | 正确 | 10 | 0.018 s | 1172 KB | 0 |
| 8 | 正确 | 10 | 0.169 s | 1172 KB | 0 |
| 9 | 正确 | 10 | 0.167 s | 1172 KB | 0 |
| 10 | 正确 | 10 | 0.167 s | 1176 KB | 0 |
运行时间 0.547 s
平均内存使用 1172 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!
3.瑞士輪 swiss
【背景】
【問題描述】
【數據範圍】
【評測結果】
在雙人對決的競技性比賽，如乒乓球、羽毛球、國際象棋中，最常見的賽制是淘汰賽和循環賽。前者的特點是比賽場數少，每場都緊張刺激，但偶然性較高。後者的特點是較爲公平，偶然性較低，但比賽過程往往十分冗長。
本題中介紹的瑞士輪賽制，因最早使用於1895 年在瑞士舉辦的國際象棋比賽而得名。
它可以看作是淘汰賽與循環賽的折衷，既保證了比賽的穩定性，又能使賽程不至於過長。
【問題描述】
2*N 名編號爲1~2N 的選手共進行R 輪比賽。每輪比賽開始前，以及所有比賽結束後，都會按照總分從高到低對選手進行一次排名。選手的總分爲第一輪開始前的初始分數加上已參加過的所有比賽的得分和。總分相同的，約定編號較小的選手排名靠前。
每輪比賽的對陣安排與該輪比賽開始前的排名有關：第1 名和第2 名、第3 名和第4名、……、第2K – 1 名和第2K 名、…… 、第2N – 1 名和第2N 名，各進行一場比賽。每場比賽勝者得1 分，負者得0 分。也就是說除了首輪以外，其它輪比賽的安排均不能事先確定，而是要取決於選手在之前比賽中的表現。
現給定每個選手的初始分數及其實力值，試計算在R 輪比賽過後，排名第Q 的選手編號是多少。我們假設選手的實力值兩兩不同，且每場比賽中實力值較高的總能獲勝。
【輸入】
輸入文件名爲swiss.in。
輸入的第一行是三個正整數N、R、Q，每兩個數之間用一個空格隔開，表示有2*N 名選手、R 輪比賽，以及我們關心的名次Q。
第二行是2*N 個非負整數s1, s2, …, s2N，每兩個數之間用一個空格隔開，其中si 表示編號爲i 的選手的初始分數。
第三行是2*N 個正整數w1, w2, …, w2N，每兩個數之間用一個空格隔開，其中wi 表示編號爲i 的選手的實力值。
【輸出】
輸出文件名爲swiss.out。
輸出只有一行，包含一個整數，即R 輪比賽結束後，排名第Q 的選手的編號。
【輸入輸出樣例】
swiss.in
2 4 2
7 6 6 7
10 5 20 15
swiss.out
1
【輸入輸出樣例說明】
| 本輪對陣 | 本輪結束後的得分 | ||||
| 選手編號 | / | ① | ② | ③ | ④ |
| 初始 | / | 7 | 6 | 6 | 7 |
| 第1 輪 | ①—④ ②—③ | 7 | 6 | 7 | 8 |
| 第2 輪 | ④—① ③—② | 7 | 6 | 8 | 9 |
| 第3 輪 | ④—③ ①—② | 8 | 6 | 9 | 9 |
| 第4 輪 | ③—④ ①—② | 9 | 6 | 10 | 9 |
對於30%的數據，1 ≤ N≤ 100；
對於50%的數據，1 ≤ N≤ 10,000；
對於100%的數據，1 ≤ N≤ 100,000，1 ≤ R≤ 50，1 ≤ Q≤ 2N，0 ≤ s1, s2, …, s2N ≤ 10^8，1 ≤ w1,
w2, …, w2N ≤ 10^8。
【分析】
這是普及組的一道難題。
首先，由於每輪比賽的次序都是由上一輪比賽完後的比分決定的，因此對於普及組的同學來說僅能使用模擬的方法來解決。容易想到的是每一輪模擬完以後快排一次，用這樣的方法，時間複雜度爲O(2Nlog2N*R),根據數據範圍可知這種思路僅能解決50%的數據。因此我們需要一種更有效的方式。
分析題意後可以發現，對於每一輪比賽過後，每一位選手都會有一種狀態，贏了或者輸了，而每一位選手比賽前都是有序的，那麼對於所有在該輪比賽中贏了或者是輸了的選手，都是有序的。即每輪比賽後，我們可以以O(N)的效率獲得勝負選手的有序隊列，對於兩組有序序列，容易想到將兩組數列歸併，歸併的效率爲O(N)，這樣，完成一輪比賽的效率從O(2Nlog2N*R)縮減至O(NR)，根據數據範圍，這樣的程序是能夠在1秒內出解的。
【我的代碼】
C++语言: Codee#24224
/*
*Problem:NOIP2011_Junior_Swiss 瑞士輪
*Author:Yee-fan Zhu
*School:Henan Experimental High School
*Method:Merge,QuickSort
*Date:2011.11.26
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
class SWISS
{
public:
int num;
int val;
int tot;
}P[200003];
int N,R,Q;
SWISS A[100001],B[100001];
int pa,pb;
int cmp(const void *a,const void *b)
{
class SWISS *c=(class SWISS *)a;
class SWISS *d=(class SWISS *)b;
if(c->tot!=d->tot)
return d->tot-c->tot;
return c->num-d->num;
}
void init()
{
scanf("%d %d %d\n",&N,&R,&Q);
N*=2;
for(int i=1;i<=N;i++)
{
P[i].num=i;
scanf("%d",&P[i].tot);
}
for(int i=1;i<=N;i++)
scanf("%d",&P[i].val);
qsort(P+1,N,sizeof(SWISS),cmp);
}
void merge()
{
int p=0;
int i=1,j=1;
while(i<=N/2&&j<=N/2)
{
if(A[i].tot>B[j].tot)
{
P[++p]=A[i++];
continue;
}
if(A[i].tot==B[j].tot)
{
if(A[i].num<B[j].num)
{
P[++p]=A[i++];
continue;
}
P[++p]=B[j++];
continue;
}
P[++p]=B[j++];
}
while(i<=N/2) P[++p]=A[i++];
while(j<=N/2) P[++p]=B[j++];
}
void work()
{
for (int i=1;i<=R;i++)
{
int j=1;
pa=0,pb=0;
while(j<N)
{
if(P[j].val>P[j+1].val)
P[j].tot++,A[++pa]=P[j],B[++pb]=P[j+1];
else
P[j+1].tot++,A[++pa]=P[j+1],B[++pb]=P[j];
j+=2;
}
merge();
}
qsort(P+1,N,sizeof(SWISS),cmp);
printf("%d\n",P[Q].num);
}
int main()
{
freopen("swiss.in","r",stdin);
freopen("swiss.out","w",stdout);
init();
work();
return 0;
}
*Problem:NOIP2011_Junior_Swiss 瑞士輪
*Author:Yee-fan Zhu
*School:Henan Experimental High School
*Method:Merge,QuickSort
*Date:2011.11.26
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
class SWISS
{
public:
int num;
int val;
int tot;
}P[200003];
int N,R,Q;
SWISS A[100001],B[100001];
int pa,pb;
int cmp(const void *a,const void *b)
{
class SWISS *c=(class SWISS *)a;
class SWISS *d=(class SWISS *)b;
if(c->tot!=d->tot)
return d->tot-c->tot;
return c->num-d->num;
}
void init()
{
scanf("%d %d %d\n",&N,&R,&Q);
N*=2;
for(int i=1;i<=N;i++)
{
P[i].num=i;
scanf("%d",&P[i].tot);
}
for(int i=1;i<=N;i++)
scanf("%d",&P[i].val);
qsort(P+1,N,sizeof(SWISS),cmp);
}
void merge()
{
int p=0;
int i=1,j=1;
while(i<=N/2&&j<=N/2)
{
if(A[i].tot>B[j].tot)
{
P[++p]=A[i++];
continue;
}
if(A[i].tot==B[j].tot)
{
if(A[i].num<B[j].num)
{
P[++p]=A[i++];
continue;
}
P[++p]=B[j++];
continue;
}
P[++p]=B[j++];
}
while(i<=N/2) P[++p]=A[i++];
while(j<=N/2) P[++p]=B[j++];
}
void work()
{
for (int i=1;i<=R;i++)
{
int j=1;
pa=0,pb=0;
while(j<N)
{
if(P[j].val>P[j+1].val)
P[j].tot++,A[++pa]=P[j],B[++pb]=P[j+1];
else
P[j+1].tot++,A[++pa]=P[j+1],B[++pb]=P[j];
j+=2;
}
merge();
}
qsort(P+1,N,sizeof(SWISS),cmp);
printf("%d\n",P[Q].num);
}
int main()
{
freopen("swiss.in","r",stdin);
freopen("swiss.out","w",stdout);
init();
work();
return 0;
}
正在连接评测机...
已连接到评测机
| GRID | 1 |
| 名称 | Flitty |
| 系统版本 | 1.00 |
| 备注 | COGS 1号评测机 Flitty |
编译成功
| 测试点 | 结果 | 得分 | 运行时间 | 内存使用 | 退出代码 |
| 1 | 正确 | 10 | 0.000 s | 4960 KB | 0 |
| 2 | 正确 | 10 | 0.000 s | 4960 KB | 0 |
| 3 | 正确 | 10 | 0.001 s | 4960 KB | 0 |
| 4 | 正确 | 10 | 0.019 s | 4960 KB | 0 |
| 5 | 正确 | 10 | 0.047 s | 4960 KB | 0 |
| 6 | 正确 | 10 | 0.123 s | 4960 KB | 0 |
| 7 | 正确 | 10 | 0.254 s | 4960 KB | 0 |
| 8 | 正确 | 10 | 0.468 s | 4960 KB | 0 |
| 9 | 正确 | 10 | 0.543 s | 4960 KB | 0 |
| 10 | 正确 | 10 | 0.612 s | 4960 KB | 0 |
运行时间 2.068 s
平均内存使用 4960 KB
测试点通过状况 AAAAAAAAAA
得分：100
恭喜你通过了全部测试点!
沒有留言:
張貼留言