Codeforces Global Round 4

心得体得:この試合を書いて、私に1つの事を発見させて、pyは1 e 6のデータを走って基本的に爆発して、やはり安定したC++を求めたほうがいいです.でもやはりpyを練習してpyを選んで書きたいです.
A - Prime Minister
n個の数字の配列を指定して、選択した数字の中でa[1]の半分を超えないように選択方法を見つけて、そして選択した数字の総和がn個の数字の和の半分以上であることを要求します.
分析:簡単なシミュレーションで、型を出して合理的でないことを見ればいいです.
コード:

k = eval(input())
a = input().split()
for i in range(k):
    a[i] = int(a[i])
tot = 0
for i in range(k):
    tot += a[i]
if k == 2:
    if a[0] > a[1]:
        print('1
1')
    else:
        print(0)
else:
    can = a[0]
    party = []
    party.append(1)
    for i in range(k):
        if a[0] >= a[i] * 2 and len(party) < k -1:
            can += a[i]
            party.append(i+1)
    if can * 2 > tot:
        print(len(party))
        for i in party:
            print(i, end = " ")
    else:
        print(0)

B - WOW Factor
わざとwを隣接する2つのvvに书いて、あなたにいくつのwowサブシーケンスがあることを闻きます.
解析:O(n)は、各アルファベットoの両端の隣接するvvの個数を飛び出し、左に右の加算を乗じます.
コード:

#include
using namespace std;
const int maxn=1e6+7;
typedef long long ll;
char s[maxn];
int l[maxn],r[maxn];
int main(){
    cin>>s;
    int n=strlen(s);
    ll tot = 0;
    l[0] = 0;
    for(int i=1;i){
        if(s[i-1]=='v'&&s[i]=='v')
            tot ++;
        l[i] = tot;
    }
    r[n-1] = 0;
    tot = 0;
    for(int i=n-1;i>=1;i--) {
        if (s[i] == 'v' && s[i - 1] == 'v')
            tot++;
        r[i - 1] = tot;
    }
    ll ans = 0;
    for(int i=0;i){
        if(s[i]=='o')
            ans += (ll)l[i] * r[i];
    }
    cout<endl;
    return 0;
}

C - Tiles
N x Mの大きい領域を与えて、あなたに1 X 1のブロックで埋めさせて、各ブロックは1つの黒い三角形と1つの白い三角形でつなぎ合わせて、しかも隣接する2つのブロックの隣接する線の所の色が同じではないことを要求して、あなたにどれだけの適当な配置の方式があることを聞いて、mod=998244353に注意します.
分析:結論を当てて、1<
コード:

mod = 998244353
 
 
def quick_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % mod
        a = a * a % mod
        b >>= 1
    return res
 
 
n, m = input().split()
n = int(n)
m = int(m)
print(quick_pow(2, n + m))

D - Prime Graph
指定された頂点の個数は、各頂点の度数が素数であり、図の辺数も素数であるように無方向図を構築させます.
解析:各頂点の度数が2になるように、各点を順番に接続します.それから輪の中の辺まで、辺の条数まで素数でいいです.
コード:

prime = []
maxn = 100000
G = []
 
def init():
    for i in range(1007):
        G.append([])
        for j in range(1007):
            G[i].append(0)
 
 
def sieve():
    for i in range(maxn):
        prime.append(1)
    prime[0] = prime[1] = 0
    for i in range(maxn):
        if prime[i]:
            j = 2 * i
            while j < maxn:
                prime[j] = 0
                j += i
 
 
init()
sieve()
n = eval(input())
tot = 0
for i in range(1, n):
    G[i][i+1] = 1
    tot += 1
G[1][n] = 1
tot += 1
j = n - 1
i = 1
while j > i:
    if prime[tot]:
        break
    G[i][j] = 1
    tot += 1
    i += 1
    j -= 1
 
print(tot)
for i in range(1, n + 1):
    for j in range(1, n + 1):
        if G[i][j]:
            print(str(i)+' '+str(j))

E - Archaeology
文字列を指定して、元の文字列の半分以上の長さの返信サブシーケンスを見つけます.
解析:直接シミュレーションでいいです.3つの位置、s[l]とs[r]、s[l-1]とs[r]、s[l]とs[r-1]を比較するだけです.
コード:

#include
using namespace std;
const int maxn=1e6+7;
char s[maxn];
bool vis[maxn];
int main() {
    cin >> s;
    int n = strlen(s);
    int l = 0, r = n - 1, cnt = 0;
    while (l <= r) {
        if (s[l] == s[r]) {
            vis[l] = vis[r] = true;
            if (l == r)
                cnt += 1;
            else
                cnt += 2;
            l += 1;
            r -= 1;
        } else if (s[l + 1] == s[r]) {
            vis[l + 1] = vis[r] = true;
            if (l + 1 == r)
                cnt += 1;
            else
                cnt += 2;
            l += 2;
            r -= 1;
        } else if (s[l] == s[r - 1]) {
            vis[l] = vis[r - 1] = true;
            if (l == r - 1)
                cnt += 1;
            else
                cnt += 2;
            l += 1;
            r -= 2;
        } else {
            r -= 1;
            l += 1;
        }
    }
    for (int i = 0; i < n; i++)
        if (vis[i])
            printf("%c", s[i]);
    return 0;
}