Codeforces Round #566 (Div. 2)

C. Beautiful Lyrics

题意：

定义“优美的歌词”如下：

由两行四个单词组成，每行两个，用空格隔开
第一行第一个单词的元音数等于第二行第一个单词的元音数
第一行第二个单词的元音数等于第二行第二个单词的元音数
每行的最后一个出现的元音相同

给定

请找到最大的

非常麻烦的模拟题比较考验码力比赛的时候一个半小时才写出了QAQ

具体没啥好说的强行模拟即可先筛两遍

#include<bits/stdc++.h>
using namespace std;
//input by bxd
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define RI(n) scanf("%d",&(n))
#define RII(n,m) scanf("%d%d",&n,&m)
#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
#define RS(s) scanf("%s",s);
#define ll long long
#define pb push_back
#define REP(i,N)  for(int i=0;i<(N);i++)
#define CLR(A,v)  memset(A,v,sizeof A)
//////////////////////////////////
#define inf 0x3f3f3f3f
const int N=1e6+5;
int n;
struct node
{
    int num,last;
    string str;
}s[N],s1[N],s2[N];
 
bool cmp(node a,node b)
{
    return a.num>b.num||a.num==b.num&&a.last<b.last;
}
 
int cnt1,cnt2,cnt3;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n;
    rep(i,1,n)
    {
        cin>>s[i].str;
        int len=s[i].str.size();
        rep(j,0,len-1)
        {
            if(s[i].str[j]=='a')
            s[i].num++,s[i].last=1;
            else if(s[i].str[j]=='e')
            s[i].num++,s[i].last=2;
            else if(s[i].str[j]=='i')
            s[i].num++,s[i].last=3;
            else if(s[i].str[j]=='o')
            s[i].num++,s[i].last=4;
            else if(s[i].str[j]=='u')
            s[i].num++,s[i].last=5;
        }
    }
    sort(s+1,s+1+n,cmp);
 
    rep(i,1,n)
    {
        if(s[i].num==s[i+1].num&&s[i].last==s[i+1].last)
        {
            s1[++cnt1]=s[i];
            s1[++cnt1]=s[i+1];
            i++;
        }
        else if(s[i].num)
        {
            s2[++cnt2]=s[i];
        }
 
    }
    sort(s2+1,s2+1+cnt2,cmp);
    rep(i,1,cnt2)
    {
        if(s2[i].num==s2[i+1].num&&s2[i].num)
        {
            s[++cnt3]=s2[i];
            s[++cnt3]=s2[i+1];
            i++;
        }
    }
    cnt2=cnt3;
    if(cnt2>=cnt1)cout<<cnt1/2;
    else cout<<cnt2/2+(cnt1-cnt2)/4  ;
    cout<<endl;
 
    if(cnt2>=cnt1)
    {
        rep(i,1,cnt1)
        {
            cout<<s[i].str<<" "<<s1[i].str<<endl;
            cout<<s[i+1].str<<" "<<s1[i+1].str<<endl;
            i++;
        }
    }
    else
    {
        rep(i,1,cnt2)
        {
            cout<<s[i].str<<" "<<s1[i].str<<endl;
            cout<<s[i+1].str<<" "<<s1[i+1].str<<endl;
            i++;
        }
        rep(i,cnt2+1,cnt1)
        {
            if(i+3>cnt1)break;
            cout<<s1[i+3].str<<" "<<s1[i].str<<endl;
            cout<<s1[i+2].str<<" "<<s1[i+1].str<<endl;
            i+=3;
        }
    }
 
    return 0;
}

View Code

E.Product Oriented Recurrence

这是一道矩阵加速的好题我之前只会加法的这个是乘法的要把乘法转化为加法

这篇博客讲的非常的好！！！！

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
 
template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}
 
template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}
 
const LL MOD = 1e9 + 7, PHI = 1e9 + 6;
LL n, f1, f2, f3, c, ans;
 
struct Matrix {
    int size;
    LL mat[6][6];
 
    Matrix(int x) {
        size = x;
        memset(mat, 0, sizeof (mat));
    }
    inline friend Matrix operator*(Matrix a, Matrix b) {//矩阵乘法 
        Matrix c(a.size);
        for (int i = 1; i <= c.size; ++i)
            for (int k = 1; k <= c.size; ++k)
                for (int j = 1; j <= c.size; ++j)
                    c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % PHI;
                    //这里对 φ(p) 取模 
        return c;
    }
} baseA(3), x(3), y(3), z(3), baseB(5), w(5);
 
inline LL quickPow(LL x, LL p) {//快速幂 
    LL res = 1;
    for (; p; p >>= 1, x = x * x % MOD)
        if (p & 1) res = res * x % MOD;
    return res;
}
 
inline Matrix quickPow(Matrix x, LL p) {//矩阵快速幂 
    Matrix res(x.size);
    for (int i = 1; i <= res.size; ++i) res.mat[i][i] = 1;//单位矩阵 
    for (; p; p >>= 1, x = x * x)
        if (p & 1) res = res * x;
    return res;
}
 
inline void build() {//构造初始矩阵和转移矩阵 
    x.mat[3][1] = y.mat[2][1] = z.mat[1][1] = 1;
    w.mat[5][1] = 2;
    baseA.mat[1][1] = baseA.mat[1][2] = baseA.mat[1][3] = 
    baseA.mat[2][1] = baseA.mat[3][2] = 1;//baseA 是 x,y,z 的转移矩阵 
    for (int i = 1; i <= 5; ++i) baseB.mat[1][i] = 1;
    baseB.mat[2][1] = baseB.mat[3][2] = baseB.mat[4][4] = 
    baseB.mat[4][5] = baseB.mat[5][5] = 1;//baseB 是 w 的转移矩阵 
}
 
int main() {
    read(n), read(f1), read(f2), read(f3), read(c);
    build();
    baseA = quickPow(baseA, n - 3), baseB = quickPow(baseB, n - 3);
    w = baseB * w, x = baseA * x, y = baseA * y, z = baseA * z;
    //求出四个答案矩阵后得到 w[n],x[n],y[n],z[n]
    ans = quickPow(c, w.mat[1][1]) * quickPow(f1, x.mat[1][1]) % MOD * 
    quickPow(f2, y.mat[1][1]) % MOD * quickPow(f3, z.mat[1][1]) % MOD;
    //快速幂合并答案 
    write(ans);
    putchar('
');
    return 0;
}

View Code