做題總結：要看清是什麼資料，格式的輸出，邊界條件，不能太過盲目而犯錯，這回還因為c題少了一個~導緻錯誤，太不應該了。
1273: 夫妻
時間限制: 1 Sec 記憶體限制: 32 MB
送出: 362 解決: 82
[送出][狀态][讨論版]
題目描述
有n對夫妻圍成一個圈站，他們每個人被連續的編号為1至2n。丈夫和妻子不一定站在一起。現在，對于一對夫妻，如果他們兩人中間沒有隔任何其他人（站在一起），那麼，他們将牽手離開。直到所有人都離開或者留下的人不能成功牽手，遊戲結束。
現在請問：是否所有的夫妻都能成功牽手走出這個圓圈呢？
輸入
輸入包含多組測試資料。每組測試資料中，第一行為一個整數n（1<=n<=100000），表示有n對夫妻。之後的n行中，每行包含兩個整數a和b，表示a與b是一對夫妻，他們初始時站的位置為a和b。
n=0表示程式終止輸入。
輸出
如果所有的夫妻都能成功牽手離開，輸出“Yes”，否則，輸出“No”。
樣例輸入
- 4
1 4
2 3
5 6
7 8
2
1 3
2 4
樣例輸出
Yes
No
提示
來源
ZSU
心得：一直想用約瑟夫環的思路來解決，發現行不通。
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
int n,i,a,b;
while(~scanf("%d",&n)&&n)
{
map <int,int> m;
m.clear();
stack <int> s;
for(i=0;i<n;i++)
{
scanf("%d%d",&a,&b);
m[a]=b;m[b]=a;
}
i=1;
while(i<=2*n)
{
if(!s.empty())
{
int tp=s.top();
if(m[tp]==i||m[i]==tp) s.pop();
else s.push(i);
}
else s.push(i);
i++;
}
if(!s.empty()) printf("No\n");
else printf("Yes\n");
}
return 0;
}
1434: 糖果迷陣
時間限制: 1 Sec 記憶體限制: 128 MB
送出: 101 解決: 49
[送出][狀态][讨論版]
題目描述
Inna 喜歡吃糖和遊戲糖果迷陣.今天，他推出了新遊戲“糖果迷陣2：重新整理”。
遊戲由一個nxm的矩陣表組成。矩陣每行包含一個帶有侏儒的單元格和一塊帶有糖果的單元格，和一些空的單元格。遊戲有多次操作，每次操作玩家需要選中所有那些侏儒沒獲得糖果的行，并發出指令“Let’s go!”.之後所有選中行的侏儒開始同時向右移動，每秒每個侏儒隻能向目前單元格的右側相鄰單元格移動一格，操作一直持續到發生以下事件之一時：
·一些侏儒到達所在行的最右邊
·一些侏儒到達糖果所在單元格獲得糖果
當所有侏儒得到糖果時結束
Inna是如此聰明得設計出這個遊戲. 可是你們呢? 你的任務是用最優的方法來完成這個遊戲，也就是用最少的操作來完成這個遊戲。
輸入
輸入的第一行包含兩個整數n和m（1≤N≤1000;2≤M≤1000）。
每個接下來的n行包含m個字元 – 代表這局的“糖果迷陣：重新整理”。字元“*”表示該領域的空白單元格，字元“G”代表一個侏儒和字元“S”代表一個糖果。矩陣不包含其他字元。這是保證每行包含一個字元“G”和一個字元“S”。
輸出
在一行列印單個整數 - 來表示完成遊戲的最優解，或-1如果目标不能在給定的遊戲場中可以實作所需的運動或最小數目。
樣例輸入
3 4
*G*S
G**S
*G*S
1 3
S*G
樣例輸出
2
-1
提示
請使用cin>>str; 或者scanf("%s",str); 輸入
來源
心得：題目了解錯了，竟然去找最少需要幾步走完。
題目意思：每次操作是G遇到S或者G走到底結束，問最少幾次操作，G走不到S則輸出-1.
注意，區分f1和f2.
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
int n,m;
while(~scanf("%d%d",&n,&m))
{
string s;
set <int> st;
st.clear();
int f1=0,cnt=0;
while(n--)
{
cin>>s;
int f2=0,i=0,k=0;
while(s[i]!='S')
{
if(s[i]=='G')
{
f2=1;
}
else if(f2==1)
{
k++;
}
i++;
}
if(!st.count(k))
{
st.insert(k);
cnt++;
}
if(f2==0) f1=1;
}
if(f1==1) cout<<-1<<endl;
else cout<<cnt<<endl;
}
return 0;
}
1783: 秋實大哥與快餐店
時間限制: 1 Sec 記憶體限制: 128 MB
送出: 73 解決: 11
[送出][狀态][讨論版]
題目描述
朝為田舍郎，暮登天子堂。秋實大哥從小就懷抱有遠大的理想，是以他開了一家快餐店。
秋實大哥根據菜的口感，給每一道菜一個唯一的CID，同時對于前來的客人，根據他們的口味喜好，秋實大哥會給每一個客人一個PID。
對于一個标号為PID的客人，他對标号為CID的菜的喜愛程度為PID∧CID(∧表示按位異或），該值越大表示越喜歡。
秋實大哥實在太忙了，現在他需要你來幫忙照看一下他的店鋪。
輸入
第一行包含一個整數n，表示秋實大哥的餐館内現在有n道菜。接下來一行包含n個整數，分别表示每一道菜的CID。
接下來一行包含一個整數m，表示接下來發生了m件事。接下來的m行，每一行為以下兩種事件之一：
0 c : 表示秋實大哥最新研制出一道标号為c的菜
1 p : 表示來了一位标号為p的客人，請你在已有的菜中找出一道他最喜愛的菜
1≤n，m≤100000，0≤PID，CID≤1000000。
輸出
對于每一個1 p事件輸出一個整數，表示該客人最喜歡的菜的标号
樣例輸入
1
1
3
1 1
0 2
1 1
樣例輸出
1
2
提示
來源
[送出][狀态][讨論版]
這道題使用二進制和字典樹的知識做的。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int maxn=10000100;
const int mod=100000100;
const int maxbit=20;
int n,m;
struct Node{
int R,L,id;
}tire[1<<22]; //字典樹的結構
int query(int x) //查找操作
{
int rt=1,tax=~x;
for(int i=1;i<=maxbit;i++)
{
if((tax>>(maxbit-i))&1)
{
if(tire[rt].R)
{
rt=rt<<1|1;
}
else
{
rt=rt<<1;
}
}
else
{
if(tire[rt].L)
{
rt=rt<<1;
}
else
{
rt=rt<<1|1;
}
}
}
return tire[rt].id;
}
void Insert(int x) //插入
{
int rt=1;
for(int i=1;i<=maxbit;i++)
{
if((x>>(maxbit-i))&1)
{
tire[rt].R=1;
rt=rt<<1|1;
}
else
{
tire[rt].L=1;
rt=rt<<1;
}
}
tire[rt].id=x;
}
int main(void)
{
int c,p,i,k;
while(~scanf("%d",&n))
{
memset(tire,0,sizeof(tire));
while(n--)
{
scanf("%d",&k);
Insert(k);
}
scanf("%d",&m);
while(m--)
{
scanf("%d%d",&c,&p);
if(c&1)
{
printf("%d\n",query(p));
}
else
{
Insert(p);
}
}
}
return 0;
}
參考文章：https://blog.csdn.net/zsc2014030403015/article/details/50767677
1751: 瑞士輪
時間限制: 1 Sec 記憶體限制: 128 MB
送出: 98 解決: 28
[送出][狀态][讨論版]
題目描述
在雙人對決的競技性比賽，如乒乓球、羽毛球、國際象棋中，最常見的賽制是淘汰賽和循環賽。前者的特點是比賽場數少，每場都緊張刺激，但偶然性較高。後者的特點是較為公平，偶然性較低，但比賽過程往往十分冗長。
本題中介紹的瑞士輪賽制，因最早使用于 1895 年在瑞士舉辦的國際象棋比賽而得名。
它可以看作是淘汰賽與循環賽的折衷，既保證了比賽的穩定性，又能使賽程不至于過長。
2*N名編号為 1~2N的選手共進行R輪比賽。每輪比賽開始前，以及所有比賽結束後，都會按照總分從高到低對選手進行一次排名。選手的總分為第一輪開始前的初始分數加上已參加過的所有比賽的得分和。總分相同的，約定編号較小的選手排名靠前。
每輪比賽的對陣安排與該輪比賽開始前的排名有關：第1 名和第2 名、第3 名和第4名、……、第2K-1名和第 2K名、…… 、第 2N-1 名和第2N名，各進行一場比賽。每場比賽勝者得 1 分，負者得 0 分。也就是說除了首輪以外，其它輪比賽的安排均不能事先确定，而是要取決于選手在之前比賽中的表現。
現給定每個選手的初始分數及其實力值，試計算在 R 輪比賽過後，排名第 Q 的選手編号是多少。我們假設選手的實力值兩兩不同，且每場比賽中實力值較高的總能獲勝。
輸入
輸入的第一行是三個正整數 N、R、Q，每兩個數之間用一個空格隔開，表示有 2*N名選手、R 輪比賽，以及我們關心的名次 Q。
第二行是 2*N個非負整數 s1, s2, …, s2N，每兩個數之間用一個空格隔開，其中 s 表示編号為 i 的選手的初始分數。
第三行是 2*N個正整數 w1, w2, …, w2N，每兩個數之間用一個空格隔開，其中 w 表示編号為 i 的選手的實力值。
輸出
輸出隻有一行，包含一個整數，即 R 輪比賽結束後，排名第 Q 的選手的編号。
樣例輸入
2 4 2
7 6 6 7
10 5 20 15
樣例輸出
1
#include<bits/stdc++.h>
using namespace std;
struct P{
int num,s,w;
};
const int INF=200020;
P a[INF],b[INF],c[INF];
int n,r,q;
bool pd(const P& a,const P& b)
{
return (a.s==b.s)?(a.num<b.num):(a.s>b.s);
}
void solve()
{
int ai=1,bi=1;
for(int i=1;i<=n*2;i+=2)
{
if(c[i].w>c[i+1].w)
{
c[i].s++;
a[ai++]=c[i];
b[bi++]=c[i+1];
}
else
{
c[i+1].s++;
a[ai++]=c[i+1];
b[bi++]=c[i];
}
}
int i=1,j=1,k=1;
while(i<ai&&j<bi)
{
if(pd(a[i],b[j]))
{
c[k++]=a[i++];
}
else
{
c[k++]=b[j++];
}
}
while(i<ai) c[k++]=a[i++];
while(j<bi) c[k++]=b[j++];
}
int main(void)
{
scanf("%d%d%d",&n,&r,&q);
for(int i=1;i<=2*n;i++)
{
scanf("%d",&c[i].s);
c[i].num=i;
}
for(int i=1;i<=n*2;i++)
{
scanf("%d",&c[i].w);
}
sort(c+1,c+1+2*n,pd);
for(int i=1;i<=r;i++)
{
solve();
}
printf("%d\n",c[q].num);
return 0;
}
1882: wjw的括号遊戲
時間限制: 1 Sec 記憶體限制: 128 MB
送出: 14 解決: 7
[送出][狀态][讨論版]
題目描述
wjw最近玩了一個很神奇的遊戲，給你n對括号，我們将字首序列中左括号的個數和右括号數的最大差稱為這個序列的深度，比如序列“()()(())”深度為2，“(()(()()))”深度為3，wjw為了表現自己的智商非常高，是以他想要知道給定括号對數n，求深度為k的方案數。
比如對n=3,k=2，存在"()(())", "(()())", "(())()"，方案數為3。
輸入
輸入檔案包含多組測試資料，每個測試資料包含兩個正數n和k(1<=k<=n<=50)
輸入資料以0 0結尾
輸出
對每個測試資料輸出深度等于k的方案數，相鄰兩組測試資料以一個空行分隔，檔案末尾不應存在空行。
樣例輸入
3 2
25 21
0 0
樣例輸出
Case 1: 3
Case 2: 175125
提示
來源
jnxxhzz
[送出][狀态][讨論版]
這道題看了很久也沒明白學長的題解，先附上連結吧：https://blog.csdn.net/jnxxhzz/article/details/54604207
![Hdu 6274（預處理+二分）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)