Codeforces #313
这次犯了好多脑残错误。
B题FST直接导致rating降了。
带两个新手打比赛。
D、E分别WA/T了。
其中都是很简单的。
解&码
A
看有没有1就行。
#include <iostream>
using namespace std;
int main()
{
int n;
cin>>n;
bool ok = false;
for(int i = 0; i < n; i++)
{
int tmp;
cin>>tmp;
if(tmp == 1)
{
ok = true;
break;
}
}
if(ok)
cout<<-1<<endl;
else
cout<<1<<endl;
return 0;
}
B
分别放两个角,四个if就行。
#include <iostream>
using namespace std;
int a1, b1, a2, b2, a3, b3;
inline bool check(int x1, int y1, int x2, int y2)
{
return !(x1 > x2 && y1 > y2) && x1 >= 0 && x2 >= 0 && y1 >= 0 && y2 >= 0 && x1 <= a1 && x2 <= a1 && y1 <= b1 && y2 <= b1;
}
int main()
{
cin>>a1>>b1>>a2>>b2>>a3>>b3;
if(check(a2, b2, a1 - a3, b1 - b3) || check(b2, a2, a1-a3,b1-b3) || check(a2,b2,a1-b3,b1-a3) || check(b2,a2,a1-b3,b1-a3))
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
return 0;
}
C
数三角。直接面积算更好。
这份是数单位三角形。
#include <iostream>
using namespace std;
int main()
{
int a, b, c, d, e, f;
cin>>a>>b>>c>>d>>e>>f;
int bian = a + b + c;
int sum = 0;
for(int i = 0, j = 1; i < bian; i++, j += 2)
sum += j;
for(int i = 0, j = 1; i < a; i++, j += 2)
sum -= j;
for(int i = 0, j = 1; i < c; i++, j += 2)
sum -= j;
for(int i = 0, j = 1; i < e; i++, j += 2)
sum -= j;
cout<<sum<<endl;
return 0;
}
面积大法。
#include <iostream>
using namespace std;
int main()
{
int a, b, c, d, e, f;
cin>>a>>b>>c>>d>>e>>f;
cout<<(a+b+c)*(a+b+c)-a*a-c*c-e*e<<endl;
return 0;
}
D
Orz暴力模拟O(n lg n)得出字符串最小之匹配即可。
#include <iostream>
#include <string>
using namespace std;
string que(string s)
{
if(s.length() % 2 == 1)
return s;
string s1, s2;
for(int i = 0; i < s.length() / 2; i++)
s1 += s[i];
for(int i = s.length() / 2; i < s.length(); i++)
s2 += s[i];
s1 = que(s1), s2 = que(s2);
return min(s1, s2) + max(s1, s2);
}
int main()
{
string s, t;
cin>>s>>t;
s = que(s);
t = que(t);
if(s == t)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
return 0;
}
E
小学奥数。组合数去模。结论在想怎么证。
结论其实很简单,一共走r+c-2步,其中r-1步向下,c-1步向右,组合选一下即是$ {r+c-2 \choose r-1} $
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int mod = 1e9 + 7;
const int maxn = 1e6 + 10, maxm = 2000 + 10;
long long factor[maxn] = {0}, d[maxm] = {0};
vector<pair<int, int> > v;
template<class T>
void read(T& x)
{
char c = getchar(); T p = 1, n = 0;
while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
x = p * n;
}
struct node
{
int r, c;
bool operator<(const node& a) const
{
return r < a.r || (r == a.r && c < a.c);
}
} black[maxm];
long long power(long long a, int n)
{
long long ans = 1;
a %= mod;
while(n > 0)
{
if(n & 1)
{
ans *= a;
ans %= mod;
}
a *= a;
a %= mod;
n >>= 1;
}
return ans;
}
int C(int m, int n)
{
return factor[m] * power(1LL * factor[n] * factor[m - n], mod - 2) % mod;
}
int main()
{
int h, w, n;
read(h), read(w), read(n);
for(int i = 0; i < n; i++)
read(black[i].r), read(black[i].c);
sort(black, black + n);
int max = h + w;
factor[0] = 1;
for(int i = 1; i <= max; i++)
factor[i] = 1LL * factor[i - 1] * i % mod;
black[n++] = (node){h, w};
for(int i = 0; i < n; i++)
{
int r = black[i].r, c = black[i].c;
d[i] = C(r + c - 2, r - 1);
for(int j = 0; j < i; j++)
{
int r1 = black[j].r, c1 = black[j].c;
if(c < c1)
continue;
d[i] -= d[j] * C(r + c - r1 - c1, r - r1) % mod;
if(d[i] < 0)
d[i] += mod;
}
}
printf("%d", d[n - 1]);
return 0;
}