2015年7月

这次犯了好多脑残错误。
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;
}

#include <iostream>
#include <cstring>
using namespace std;
const int maxm = 10 + 5,  mod = 10000007;
class Matrix
{
public:
    long long a[maxm][maxm];
    int n, m;

    Matrix(int _n, int _m) : n(_n), m(_m){memset(a, 0, sizeof a);}
    void init(){memset(a, 0, sizeof a);}
    void identity(){for(int i = 0; i < n; i++) a[i][i] = 1;}

    Matrix operator*(const Matrix& b)
    {
        Matrix ret(n, b.m);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < b.m; j++)
                for(int k = 0; k < m; k++)
                {
                    ret.a[i][j] += a[i][k] * b.a[k][j];
                    ret.a[i][j] %= mod;
                }
        return ret;
    }

    Matrix operator^(int p)
    {
        Matrix ret(n, n);
        ret.identity();
        while(p > 0)
        {
            if(p & 1)
                ret = ret * *this;
            *this = *this * *this;
            p >>= 1;
        }
        return ret;
    }
};
int main()
{
    int n, m;
    while(cin>>n>>m)
    {
        Matrix a(n + 2, 1);
        a.a[0][0] = 23;
        a.a[n + 1][0] = 3;
        for(int i = 1; i <= n; i++)
            cin>>a.a[i][0];
        Matrix b(n + 2, n + 2);
        for(int i = 0; i < n + 2; i++)
            for(int j = 0; j < n + 2; j++)
            {
                if(j == 0 && i != n + 1)
                    b.a[i][j] = 10;
                else if((i != n + 1 && j <= i) || j == n + 1)
                    b.a[i][j] = 1;
            }
        b = b ^ m;
        b = b * a;
        //while(b.a[n][0] < 0)
        //    b.a[n][0] += mod;
        cout<<b.a[n][0] % mod<<endl;
    }
    return 0;
}
//Orz WHJ