2015年7月

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;
}

HDU 5015

#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
bst g22 jinniu lilai opebet orange88 vinbet xbet yuebo zunlong shijiebei bet007 hg0088 ju111 letiantang m88 mayaba qg777 qianyiguoji sbf777 tengbohui tlc ule weilianxier waiweitouzhu xingfayule xinhaotiandi yinheyule youfayule zhongying 2018shijiebei w88 18luck 188bet beplay manbet 12bet 95zz shenbo weide1946 ca88 88bifa aomenxinpujing betway bodog bt365 bwin tongbao vwin weinisiren 88jt fenghuangyule hongyunguoji 918botiantang huanyayule jianada28 jixiangfang libo long8 hongzuyishi zuqiutouzhu