A. Dima and Continuous Line
链接：http://codeforces.com/contest/358/problem/A
描述：给一个n [1, 10^3], 然后是n个点横坐标xi [-10^6, 10^6]，每相邻的两个点是一个半圆直径的两个点。判断这些圆会不会相交。相交输出yes，否则输出no。
思路：数据规模很小，直接暴力15ms水过。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
struct Circus {
int left, right;
bool operator< (const Circus &next) const
{
return (left < next.left) || (left == next.left && right < next.right);
}
};
bool IsInsect(const Circus &a, const Circus &b)
{
return (a.left < b.left) && (b.left < a.right) && (a.right < b.right);
}
int main()
{
int n;
while (scanf("%d", &n) != EOF)
{
int a[n];
for (int i = 0; i < n; ++i)
scanf("%d", &a[i]);
if (n == 1)
{
cout << "no" << endl;
continue;
}
Circus cir[n];
for (int i = 0; i < n - 1; ++i)
{
cir[i].left = min(a[i], a[i+1]);
cir[i].right = max(a[i], a[i+1]);
}
sort(cir, cir + n);
bool flag = 0;
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (IsInsect(cir[i], cir[j]))
{
flag = 1;
break;
}
if (flag)
cout << "yes\n";
else
cout << "no\n";
}
return 0;
}
B. Dima and Text Messages
链接:http://codeforces.com/contest/358/problem/B
描述：第一行是一个n [1, 10^5], 然后是n个字符串，首先按照规则在每个相邻字符串之间加上<3,（首位也要加上），得到<3word1<3word2<3
... wordn<3。然后在得到的字符串上任意位置添加任意个小写字母或数字或大于小于号。现在输入一个字符串text，判断此字符串是否是按照规则构成的。是则输出yes，or
no。
思路：先按照规则生成<3word1<3word2<3
... wordn<3这个字符串。然后进行离散的匹配。只要它的每个字符都在text中出现就yes。
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
inline bool IsLegal(char c)
{
return ((c >= 'a' && c <= 'z') || (c >= '0' && c <= '9') || c == '<' || c == '>');
}
int main()
{
int n;
scanf("%d", &n);
string s("<3"), t, text;
while (n--)
{
cin >> t;
s += t;
s += "<3";
}
cin >> text;
int lens = s.size(), lentxt = text.size();
if (lentxt < lens) //text长度小于s时一定不行
{
printf("no\n");
return 0;
}
for (int i = 0; i < lentxt; ++i) //判断每个字符是否合法
if (!IsLegal(text[i]))
{
printf("no\n");
return 0;
}
int i = 0, j = 0; //i，j分别作为s和text下标
while (true)
{
if (j >= lentxt)
break;
while (text[j] != s[i] && j < lentxt) //直到找到s[i]==text[j],一个匹配
++j;
++i, ++j; //找到一个匹配后就同时递增找下一个
}
//最后i小于s的长度时，说明没有匹配完全s中的每一个，输出no
if (i >= lens) //有可能出现前面都匹配，这时候i大于lens，一开始用==wa了一次
printf("yes\n");
else
printf("no\n");
return 0;
}
C. Dima and Containers
链接：http://codeforces.com/contest/358/problem/C
描述：操作三个数据结构使得每次取出的结果最大。具体请看题目。
思路：我把最大的三个记录，剩下的就直接放到deck的队尾。这一题自己思路不是很好，虽然过了，但是代码写的很烂。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <string>
using namespace std;
struct T {
int index, val;
string ope;
T(int index, int val, string s) : index(index), val(val), ope(s) { }
};
bool cmpind(const T &a, const T &b)
{ return a.index < b.index; }
bool cmpval(const T &a, const T &b)
{ return a.val < b.val; }
int main()
{
int n, a;
scanf("%d", &n);
vector<T> t;
int ind = 0;
while (n--)
{
scanf("%d", &a);
if (a != 0)
{
t.push_back(T(ind++, a, ""));
}
int k = t.size();
if ((a == 0 && !t.empty()) || (a != 0 && n == 0 && !t.empty()))
{
if (k > 3)
{
sort(t.begin(), t.end(), cmpval);
vector<T>::iterator it;
for (it = t.begin(); it != t.end() - 3; ++it)
it->ope = "pushBack";
t[k-1].ope= "pushFront", t[k-2].ope = "pushQueue", t[k-3].ope = "pushStack";
sort(t.begin(), t.end(), cmpind);
for (it = t.begin(); it != t.end(); ++it)
cout << it->ope << endl;
}
else if (k == 3)
printf("pushBack\npushQueue\npushStack\n");
else if (k == 2)
printf("pushBack\npushQueue\n");
else if (k == 1)
printf("pushBack\n");
t.clear();
}
if (a == 0 && t.empty())
{
ind = 0;
if (k >= 3)
printf("3 popFront popQueue popStack\n");
else if (k == 2)
printf("2 popFront popQueue\n");
else if (k == 1)
printf("1 popFront\n");
else
printf("0\n");
t.clear();
}
}
return 0;
}