做题总结：要看清是什么数据，格式的输出，边界条件，不能太过盲目而犯错，这回还因为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=)