2019-07-21 21:59 山东大学 Java

关注

CF1178 解题报告

A

题意

给出一个长度为 $n(2 \le n \le 100)$ 的序列 $a$ 。选出他的一个子序列 $b$ 。满足下列条件。

必须选择 $a_1$

对于所有的 $2 \le i \le tot$ ( $tot$ 为所选序列的长度)都有 $b_1 \le 2b_i$

$2\sum\limits_{i=1}^{tot}b_i > \sum\limits_{i=1}^na_i$

输出一个符合条件的子序列。

solve

将所有满足 $2a_i \le a_1$ 的都选上。如果无法达到条件3，说明无解。否则输出。

code

/*
* @Author: wxyww
* @Date:   2019-07-20 23:34:52
* @Last Modified time: 2019-07-21 07:52:08
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 110;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int SUM,a[N],bz[N],num;
int main() {
    int n = read();
    for(int i = 1;i <= n;++i)     a[i] = read(),SUM += a[i];
    num = a[1];
    bz[1] = 1;
    int tot = 1;
    for(int i = 2;i <= n;++i) if(a[i] * 2 <= a[1]) ++tot,bz[i] = 1,num += a[i];

    if(num * 2 <= SUM) {puts("0");return 0;}
    printf("%d\n",tot);
    for(int i = 1;i <= n;++i) if(bz[i]) printf("%d ",i);
    return 0;
}

B

题意

给出一个只含 $'v','o'$ 的字符串。相邻的两个 $'v'$ 可以看做是一个 $'w'$ ，问可以组成 $'wow'$ 的子序列数量。

solve

正反各做一遍前(后)缀和。然后枚举 $'o'$ ，统计答案即可。

code

/*
* @Author: wxyww
* @Date:   2019-07-21 07:52:15
* @Last Modified time: 2019-07-21 08:08:24
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 1000000 + 100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
char s[N];
ll sum1[N],sum2[N],ans;

int main() {
    scanf("%s",s + 1);
    int n = strlen(s + 1);
    for(int i = 2;i <= n;++i) {
        sum1[i] = sum1[i - 1];
        if(s[i] == 'v' && s[i - 1] == 'v') sum1[i]++;
    }
    for(int i = n - 1;i >= 1;--i) {
        sum2[i] = sum2[i + 1];
        if(s[i] == 'v' && s[i + 1] == 'v') sum2[i]++;
    }
    for(int i = 1;i <= n;++i) if(s[i] == 'o') ans += sum2[i] * sum1[i];
    cout<<ans;
    return 0;
}

C

题意

有一个 $w\times h(1\le w,h \le 1000)$ 的房间。要在里面铺下图所示的瓷砖(长宽均为1),可以旋转。要求两块相邻的边两边的颜色不同。问方案数。答案对 $998244353$ 取模
enter description here

solve

当房间相邻的两条边的瓷砖确定了之后。其他的所有瓷砖就也已经确定了。考虑到瓷砖间的相互影响，边缘铺的第一个瓷砖有 $4$ 种方案。其他的均有 $2$ 种方案。所以答案为 $4 \times 2^{w + h - 2}=2^{w+h}$

code

/*
* @Author: wxyww
* @Date:   2019-07-20 23:52:11
* @Last Modified time: 2019-07-21 07:52:45
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 1010;
const int mod = 998244353;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int f[N][N][4];
ll qm(ll x,ll y) {
    ll ret = 1;
    for(;y;y >>= 1,x = x * x % mod) 
        if(y & 1)ret = ret * x % mod;
    return ret;
}
int main() {
    int n = read(),m = read();
    cout<<qm(2,n + m);

    return 0;
}

D

题意

构造一张有 $n(3\le n\le 1000)$ 个点的无向图(无重边和自环)。满足:

边的总数为素数

所有点的度数均为素数

输出方案

solve

如果所有点的度数确定了。那么边数就是度数之和的一半。连边就很简单了。

所以考虑怎么确定点的度数。

猜想:必有至少一个 $A \in [2n,3n] (3 \le n \le 1000)$ 满足 $\frac{A}{2}$ 为素数。

经测试，成立。

所以可以让所有点的度数都为 $2$ 或 $3$ 只要找到这个 $A$ 作为度数之和。然后边数就是 $\frac{A}{2}$ 。

设度数为 $2$ 的点有 $x$ 个，度数为 $3$ 的点有 $y$ 个。
列方程：

$\left\{ \begin{aligned} 2x + 3y = A \\ x + y = n \end{aligned} \right.$

将所有点连成一个环之后，再连 $y$ 条边即可。

code

/*
* @Author: wxyww
* @Date:   2019-07-21 00:20:04
* @Last Modified time: 2019-07-21 07:53:25
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 1000000 + 100;
#define pi pair<int,int>
int cnt;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int tot,dis[N],vis[N],a[N],K;
void Eur() {
    for(int i = 2;i <= K;++i) {
        if(!vis[i]) dis[++tot] = i;
        for(int j = 1;j <= tot && 1ll * dis[j] * i <= K;++j) {
            vis[dis[j] * i] = 1;
            if(i % dis[j] == 0) break;
        }
    }
}    
int A;
pi ans[N];
priority_queue<pi>q;
int p(int x) {
    if(x & 1) return x + 1;
    return x;
}
int main() {
    int n = read();
    K = 100000;
    Eur();
    for(A = n * 2;A <= n * 3;A ++) {
        if(A & 1) continue;
        if(!vis[A / 2]) break;
    }

    int Y = A - n * 2;
    int X = n - Y;

    for(int i = 1;i <= X;++i) q.push(make_pair(2,i));
    for(int i = X + 1;i <= n;++i) q.push(make_pair(3,i));

    for(int i = 1;i < n;++i) ans[++cnt] = make_pair(i,i + 1);

    ans[++cnt] = make_pair(n,1);

    Y /= 2;
    for(int i = 1;i <= n;i ++) {
        if(Y && !a[i] && !a[i + 2]) ans[++cnt] = make_pair(i,i + 2),Y--,a[i] = a[i + 2] = 1;
    }

    printf("%d\n",cnt);
    for(int i = 1;i <= cnt;++i) {
        printf("%d %d\n",ans[i].first,ans[i].second);
    }

    return 0;
}

E

题意

有一个长度为 $n(2\le n \le 10^6)$ 字符串 $s$ ，只含有 $'a','b','c'$ 三种字符。选出一个长度大于等于 $\lfloor \frac{n}{2} \rfloor$ 的子回文串(不需要连续)

solve

从左右开始每次两边各找2个字符。这4个字符中，一定至少有一个出现次数大于1.将这个字符放入回文子串中。

code

/*
* @Author: wxyww
* @Date:   2019-07-21 01:31:22
* @Last Modified time: 2019-07-21 07:51:47
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;

ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
const int N = 1000000 + 10;
int n;
char s[N];
char ans[N];
int a[4],cnt;
int main() {
    scanf("%s",s + 1);
     n = strlen(s + 1);
     int l = 1,r = n - 1,bz = 0;
     while(l + 1 < r) {
         a[0] = a[1] = a[2] = 0;
         a[s[l] - 'a']++;
         a[s[l + 1] - 'a']++;
         a[s[r] - 'a']++;
         a[s[r + 1] - 'a']++;
         for(int i = 0;i <= 2;++i) {
             if(a[i] > 1) {
                 ans[++cnt] = i + 'a';
                 break;
             }
         }
         l += 2;r -= 2;
     }
     for(int i = 1;i <= cnt;++i)     putchar(ans[i]);
     if(l <= r) putchar(s[r]);
     for(int i = cnt;i >= 1;--i) putchar(ans[i]);
    return 0;
}

F1

题目链接

题意

有个长度为 $m$ 公分的布，要在上面每公分都染上颜色，整块布染恰好 $n(n=m)$ 种颜色。颜色标号从 $1$ 到 $n$ 。染色需遵循:

1.从颜色 $1$ 到颜色 $n$ 依次，即必须先染标号小的颜***r>2.每次可以染任意一个区间，但必须满足这个区间之前的颜色是相同的。

询问将这块布染成所给颜色的方案数。

solve

区间 $dp$ 。

$f[l][r]$ 表示染好 $[l,r]$ 这个区间的方案数。 $g[l][r]$ 表示最小的颜色最后单独染的方案数。

所以就有 $g[l][r] = f[l][t-1] \times f[t+1][r]$ ,( $a[t]$ 为区间 $[l,r]$ 中的最小值)

然后枚举一个 $k$ 表示 $[l,k]$ 全染成最小颜色值的方案数。

那么就有 $f[i][j]=\sum\limits_{k=l}^{r-1}g[l][k]\times f[k+1][r]$

最后 $f[1][n]$ 即为答案。

code

/*
* @Author: wxyww
* @Date:   2019-07-21 09:01:13
* @Last Modified time: 2019-07-21 10:48:02
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int N = 510,mod = 998244353;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int a[N],f[N][N],g[N][N];
int main() {
    int n = read(),m = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    a[0] = 1e9;
    for(int i = 1;i <= n + 1;++i) g[i][i] = f[i][i] = f[i][i - 1] = g[i][i - 1] = 1;
    for(int len = 2;len <= n;++len) {
        for(int l = 1;l + len - 1 <= n;++l) {
            int r = l + len - 1,t = 0;
            for(int k = l;k <= r;++k) if(a[k] < a[t]) t = k;
            f[l][r] = g[l][r] = 1ll * f[l][t - 1] * f[t + 1][r] % mod;

            for(int k = l;k < r;++k) {
                f[l][r] = (f[l][r] + 1ll * g[l][k] * f[k + 1][r] % mod) % mod;
            }
        }
    }
    cout<<f[1][n];
    return 0;
}