前言

离ak最近的1场qwq

写了9题,再给我5min就能ak的

混了个rk20多qwq

怎么天天出原题啊我做过的都有3道了

A

做法 : 小学奥数

小学奥数题吧...
只要你智商在线,人脑里模拟一下不就行了
显然也就那么几种情况。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 10000100

ll n, m;

int main() {
    scanf("%lld%lld", &n, &m);
    if(n > m * 9 || n < m * 6) return puts("jgzjgzjgz"), 0;
    ll c = n - m * 6;
    if(c > m) puts("0");
    else printf("%lld\n", m - c);
    return 0;
}

B

做法:暴力/二分

一眼秒是二分。
具体做法是二分天数,然后等差数列求和判断。
但是写挂了不知道是溢出了还是什么。赛后交了是90分。
最后一个大爷告诉我暴力能过...
怪不得是全场通过最多

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
#define N 5000050
  
ll n, m, d, x;
  
bool check(ll x) {
    __int128 s = (__int128)(x * d + n + n) * x / 2;
    return s >= (__int128)m;
}
  
int main() {
    scanf("%lld%lld%lld%lld", &n, &m, &d, &x);
    ll ans = 0, res = 0;
    while(res < m) {
        res += n;
        n += d;
        ans++;
    }
    printf("%lld\n", ans);
}

C

做法:贪心

因为没啥特殊性质,显然直接按涂上去的价值排序就好,然后取前n大的价值即可
是个sb题

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 10000100
int n, m;
struct Node {
    int a, b;
} a[N];
 
bool operator < (Node a, Node b) {
    return a.b > b.b;
}
 
int main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; ++i) scanf("%d", &a[i].a);  for(int i = 1; i <= m; ++i) scanf("%d", &a[i].b);
    sort(a + 1, a + m + 1);
    ll ans = 0;
    for(int i = 1; i <= m; ++i) {
        if(n >= a[i].a) {
            ans += 1ll * a[i].a * a[i].b;
            n -= a[i].a;
        } else {
//            if(!n) break;
            ans += 1ll * a[i].b * n;
            break;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

D

做法:贪心

之前做过类似的题,貌似是洛谷月赛。
绝对值小于等于1,很麻烦,所以不如钦定每一堆只要能拿就一定拿完,如果有一个要凑的就从右边拿。
这个正确性挺显然的吧,如果不是很理解可以把样例画出来自己看看

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
#define N 5000050
 
int n;
ll a[N];

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    ll ans = 0;
    for(int i = 1; i <= n; ++i) {
        ans += a[i] / 2;
        if(a[i] % 2 == 0) continue;
        if(a[i + 1] == 0) continue;
        ans++; a[i + 1]--;
    }
    printf("%lld\n", ans);
}

E

做法:二维前缀和

sb题啊。。。
一开始以为是个神仙题。我看错了题意以为d是每次给定的,结果是先给的。。。
那么就和NOIP2016组合数问题基本一样了
怎么天天出原题啊
预处理\(sum[i][j]\)表示前\([i,j]\)个格子,满足值大于等于d的有多少个。
那么按二维前缀和的思路容斥一下就好。如果不了解二维前缀和的看一下下面这个式子也就懂了
\(sum[l2][r2] + sum[l1 - 1][r1 - 1] - sum[l1 - 1][r2] - sum[l2][r1 - 1]\)
实在不行再画个图?那图网上找找就好,烂大街的图
至于\(n*m<1e6\)开个vector就好
据说卡空间,不过我是没给卡到

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <deque>
#include <map>
#include <set>

#define ll long long
#define inf 0x3f3f3f3f
#define il inline

namespace io {

    #define in(a) a=read()
    #define out(a) write(a)
    #define outn(a) out(a),putchar('\n')

    #define I_int ll
    inline I_int read() {
        I_int 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 F[ 200 ] ;
    inline void write( I_int x ) {
        if( x == 0 ) { putchar( '0' ) ; return ; }
        I_int tmp = x > 0 ? x : -x ;
        if( x < 0 ) putchar( '-' ) ;
        int cnt = 0 ;
        while( tmp > 0 ) {
            F[ cnt ++ ] = tmp % 10 + '0' ;
            tmp /= 10 ;
        }
        while( cnt > 0 ) putchar( F[ -- cnt ] ) ;
    }
    #undef I_int

}
using namespace io ;

using namespace std ;

#define N 1000100

int n, m, d;
vector<int>sum[N];

int main() {
    n = read(), m = read(), d = read();
    for(int i = 1; i <= n; ++i) sum[i].push_back(0); for(int i = 0; i <= m; ++i) sum[0].push_back(0);
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            int x = read();
            x < d ? sum[i].push_back(0) : sum[i].push_back(1);
        }
    } 
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
        }
    }
    int Q = read();
    while(Q--) {
        int l1 = read(), r1 = read(), l2 = read(), r2 = read();
        int ans = sum[l2][r2] + sum[l1 - 1][r1 - 1] - sum[l1 - 1][r2] - sum[l2][r1 - 1];
        printf("%d\n", ans);
    }
    return 0;
}

F

做法:搜索+构造

唯一的难题。
大致做法是宽搜一下,因为其实合法的构造方案很少。
结束了就弃了没写,这题具体做法还是看看官方题解吧。。。

G

做法:按位贪心

挺显然的一道题,3min秒了,然后因为上界搞错调了要1h。
或的规则是有1则1,那么考虑每一位,如果\(b-a\)(即a到b变换了的位数,这中间肯定有1)比这一位大,那么显然就会有一个1跟他或一下,那么这一位就固定为1了
上界要枚举到62...我上界试了31,32,63都挂了...最后62就过了,有毒

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
#define N 5000050
  
ll a, b;

int main() {
    while(~scanf("%lld%lld", &a, &b)) {
        ll ans = b | a;
        for(ll k = 63; k >= 0; k--) {
            if((ll)(1ll << (k)) <= (b - a)) ans |= (1ll << (k));
        }
        printf("%lld\n", ans);
    }
}
/*
枚举每一位
对于一位k,如果(a-b)>=(1<<k),那么这一位就可以|1
*/

H

做法:暴力枚举+线段树优化

这题做了好久...做完这题,F时间就不够了...
一开始没啥思路,然后蔡队在牛客群上说了:“H有啥难的,暴力枚举啊”
orz。
然后往这方面想了想就想出来了。
显然比较麻烦的就是这个全体右移k位。
如果我们知道了一共要右移x次,那么其实每头猪的最小代价其实是确定了的,就是\(min(a_i,min(a_{i-x}...a_{i-1})+x)\)(这是因为我们可以安排放入这头猪的时间,比如我们要取\(i-2\)这个地方的代价来填\(i\)这个位置,那么我们在剩下两次右移次数的时候放入\(i-2\)这个地方就好了。如果要用原来的价值,那么全部右移完后再放进去就好)
所以现在就明朗了。
枚举右移次数k,对于每个k算出最小代价,使用数据结构求区间最小值就可以了。
我一开始st表写挂了。。。爆了4发。最后用了线段树过了。
至于n右移了会到1的,可以分类讨论一下,也可以直接断环成链。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100010
const ll inf = 1e18;
#define int long long

int n, x;
int a[N];

struct tree{
    int l,r,mn;
}t[N<<2];
#define mid ((l + r) >> 1)
#define lc (rt << 1)
#define rc (rt << 1 | 1)
void pushup(int rt) {
    t[rt].mn = min(t[lc].mn, t[rc].mn);
}
void build(int l, int r, int rt) {
    t[rt].l = l; t[rt].r = r;
    if(l == r) {
        t[rt].mn = a[l];
        return;
    }
    build(l, mid, lc); build(mid + 1, r, rc); pushup(rt);
}
#define l t[rt].l
#define r t[rt].r
int query(int L, int R, int rt) {
    if(L <= l && r <= R) {
        return t[rt].mn;
    }
    int ans = inf;
    if(L <= mid) ans = min(ans, query(L, R, lc));
    if(R > mid) ans = min(ans, query(L, R, rc));
    return ans;
}
#undef l
#undef r
#undef mid
#undef lc
#undef rc

signed main() {
    scanf("%lld%lld", &n, &x);
    for(int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
    build(1, n, 1);
    ll ans = 1e18;
    for(int k = 0; k <= n; ++k) {
        ll sum = k * x;
        for(int i = 1; i <= n; ++i) {
            if(i - k < 1) sum += min(query(1, i, 1), query(n - k + i, n, 1));
            else sum += query(i - k, i, 1);
        }
        ans = min(ans, sum);
    }
    printf("%lld\n", ans);
    return 0;
}

I

栈(括号序列)

本质上就是个括号序列
因为注意到每次最多只能+10分,最少+5分(+0我们肯定不会去选他)。
而且每个得分需要的次数是一样的。于是我们有一个贪心的做法。每次把当前数和栈顶比较,如果可以匹配则弹出并将答案+10,如果不行就扔进栈里。
最后把栈里的两两弹出并+5即可
抽象一下,就是个括号序列匹配而已

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
#define N 1000010
  
char s[N];
int st[N];

int main() {
    scanf("%s", s + 1);
    int ans = 0, n = strlen(s + 1), top = 0;
    for(int i = 1; i <= n; ++i) {
        if(!top) {
            st[++top] = s[i] - '0';
            continue;
        }
        if(s[i] - '0' == st[top]) {
            top--;
            ans += 10;
        } else {
            st[++top] = s[i] - '0';
        }
    }
    while(top) {
        top -= 2;
        ans += 5;
    }
    printf("%d\n", ans);
}

J

做法:搜索

直接搜就行了。。。
因为是原题所以我就懒得写了,我拿了我以前写过的那题的代码交了,用的spfa。
原题是CF1064D
http://codeforces.com/contest/1064/problem/D
正好我当时打过。。。

#include <cstdio>
#include <cstring>
#include <algorithm>

#define ll long long
#define debug printf("233\n")
#define inf 0x3f3f3f3f 
#define il inline 
#define in1(a) read(a)
#define in2(a,b) in1(a),in1(b)
#define in3(a,b,c) in2(a,b),in1(c)
#define in4(a,b,c,d) in2(a,b),in2(c,d)

inline void read( int &x ){
    x = 0 ; int f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) {
        if( c == '-' ) f = -1 ;
        c = getchar() ;
    }
    while( c >= '0' && c <= '9' ) {
        x = (x << 1) + (x << 3) + c - 48 ;
        c = getchar() ;
    }
    x *= f ;
}

inline void readl( ll &x ){
    x = 0 ; ll f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) {
        if( c == '-' ) f = -1 ;
        c = getchar() ;
    }
    while( c >= '0' && c <= '9' ) {
        x = (x << 1) + (x << 3) + c - 48 ;
        c = getchar() ;
    }
    x *= f ;
}

using namespace std ;

#define N 2010

int n , m , r , c , x , y ;
char ch[ N ][ N ] ;
struct edge {
    int to , nxt , v ;
} e[ N * N * 4 ] , E[ N * N * 4 ];
int head[ N * N ] , cnt , Head[ N * N ] , Cnt ;
int vis[ N * N ] , d[ N * N ] , Vis[ N * N ] , D[ N * N ] ;
int q[ 1000100 ] ;

void ins1( int u , int v , int w ) {
    e[ ++ cnt ].to = v ;
    e[ cnt ].nxt = head[ u ] ;
    e[ cnt ].v = w ;
    head[ u ] = cnt ;
}

void ins2( int u , int v , int w ) {
    E[ ++ Cnt ].to = v ;
    E[ Cnt ].nxt = Head[ u ] ;
    E[ Cnt ].v = w ;
    Head[ u ] = Cnt ;
}

void spfa() {
    int s = (r-1) * m + c ;
    q[ 1 ] = s ;
    int l = 1 , r = 2 ;
    for( int i = 1 ; i <= n * m ; i ++ ) d[ i ] = inf ;
    d[ s ] = 0 ;
    vis[ s ] = 1 ;
    while( l != r ) {
        int u = q[ l ++ ] ;
        vis[ u ] = 0 ;
        if( l == 1000000 ) l = 1 ;
        for( int i = head[ u ] ; i ;  i = e[ i ].nxt ) {
            int v = e[ i ].to ;
            if( d[ v ] > d[ u ] + e[ i ].v ) {
                d[ v ] = d[ u ] + e[ i ].v ;
                if( !vis[ v ] ) {
                    vis[ v ] = 1 ; 
                    q[ r ++ ] = v ;
                    if( r == 1000000 ) r = 1 ;
                }
            }
        }
    }
}

void spfa2() {
    int s = (r-1) * m + c ;
    int l = 1 , r = 2 ;
    q[ 1 ] = s ;Vis[ s ] = 1 ;
    for( int i = 1 ; i <= n * m ; i ++ ) D[ i ] = inf ;
    D[ s ] = 0 ;
    while( l != r ) {
        int u = q[ l ++ ] ;
        Vis[ u ] = 0 ;
        if( l == 1000000 ) l = 1 ;
        for( int i = Head[ u ] ; i ;  i = E[ i ].nxt ) {
            int v = E[ i ].to ;
            if( D[ v ] > D[ u ] + E[ i ].v ) {
                D[ v ] = D[ u ] + E[ i ].v ;
                if( !Vis[ v ] ) {
                    Vis[ v ] = 1 ; 
                    q[ r ++ ] = v ;
                    if( r == 1000000 ) r = 1 ;
                }
            }
        }
    }
}

int main(){
    in2( n , m ) ;
    in2( r , c ) ;
    in2( x , y ) ;
    for( int i = 1 ; i <= n ; i ++ ) {
        scanf( "%s" , ch[ i ] + 1 ) ;
    }
    for( int i = 1 ; i <= n ; i ++ ) {
        for( int j = 1 ; j <= m ; j ++ ) {
            if( ch[ i ][ j ] == '*' ) continue ;
            if(i-1>=1&&ch[i-1][j]=='.') ins1((i-1)*m+j,(i-2)*m+j,0),  ins2((i-1)*m+j,(i-2)*m+j,0);
            if(j-1>=1&&ch[i][j-1]=='.') ins1((i-1)*m+j,(i-1)*m+j-1,1),ins2((i-1)*m+j,(i-1)*m+j-1,0);
            if(i+1<=n&&ch[i+1][j]=='.') ins1((i-1)*m+j,i*m+j,0),      ins2((i-1)*m+j,i*m+j,0);
            if(j+1<=m&&ch[i][j+1]=='.') ins1((i-1)*m+j,(i-1)*m+j+1,0),ins2((i-1)*m+j,(i-1)*m+j+1,1);
        }
    }
    spfa() ;
    spfa2() ;
    int ans = 0 ;
    for( int i = 1 ; i <= n * m ; i ++ ) {
        if( d[ i ] <= x && D[ i ] <= y ) ans ++ ; 
    }
    printf( "%d\n" , ans ) ;
}