周六

· · 个人记录

周六牛客

A

暴力枚举

#include<iostream>
#define ll long long

using namespace std ;

const int N = 1e6 + 10 ;

ll n , a[N] , ans ;

int main () {
    ios :: sync_with_stdio(false) ;
    cin.tie(0) , cout.tie(0) ;

    cin >> n ;

    for(int i=1; i<=n; i++) {
        ll t ; cin >> t ;
        a[t] ++ ;
    }

    for(int i=0; i<=N-1; i++) {
        ans += a[i] * a[i];
    }

    cout << ans ;

    return 0 ;
}

B

贪心 ： 先认为所有苹果都白天吃，然后选出k天晚上吃，因此按照晚上减白天的值从大到小贪心

#include<iostream>
#include<algorithm>
#define int long long

using namespace std ;

const int N = 1e5 + 10 ;

int n , k , ans ;

struct node{
    int a , b , c ;
    bool operator < ( const node t) {
        return this -> c < t.c ;
    }
}p[N];

signed main () {

    ios :: sync_with_stdio(false) ;
    cin.tie(0) , cout.tie(0) ;

    cin >> n >> k ;

    for(int i=1; i<=n; i++) {
        cin >> p[i].a >> p[i].b ;
        p[i].c = p[i].b - p[i].a ;
    }

    sort ( p + 1 , p + 1 + n ) ;

    for(int i=n,cnt=1; i; i--,cnt++) {
        if(cnt <= k) ans += p[i].b ;
        else ans += p[i].a ;
    }

    cout << ans ;

    return 0 ;
}

C

枚举，将每个插入的点对行、列、对角线的影响记录，出现负数加n

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std ;

const int N = 1e6 + 10 ;

int n , T , x , y  ;
bool row[N] , col[N] ;
bool sum[N*2] , sub[N*2] ;

int main () {

    ios :: sync_with_stdio(false) ;
    cin.tie(0) , cout.tie(0) ;

    cin >> n >> T ;

    while( T -- ) {
        cin >> x >> y ;
        int t = ( x - y ) + N ;
        if(row[x] || col[y] || sum[x+y] || sub[t]) {
            cout << "No" << endl ;
        }
        else {
            cout << "Yes" << endl ;
            row[x] = true ;
            col[y] = true ;
            sum[x + y] = true ;
            sub[t] = true ;
        }

    }

    return 0 ;
}

D

数学，在直线上方带入方程大于0，下方小于0，根据这点可判断每个点的位置

#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long

using namespace std ;

ll n , ae , be , ce , ar , br , cr , a[4] ;

signed main () {

    ios :: sync_with_stdio(false) ;
    cin.tie(0) , cout.tie(0) ;

    cin >> n ;

    cin >> ae >> be >> ce ;

    cin >> ar >> br >> cr ;

    while( n -- ) {
        ll x , y ; cin >> x >> y ;
        ll t1 = ae * x + be * y + ce ;
        ll t2 = ar * x + br * y + cr ;
        if(t1 < 0 && t2 < 0) a[0] ++ ;
        else if(t1 > 0 && t2 < 0) a[1] ++ ;
        else if(t1 > 0 && t2 > 0) a[2] ++ ;
        else a[3] ++ ;
    }

    sort( a , a + 4 ) ;

    for(int i=0; i<4; i++) cout << a[i] << ' ' ;

    return 0 ;
}

E

四维背包问题，可以优化第一维

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>

using namespace std ;

const int N = 110 , M = 30 ;

int f[M][M][M][M] ;

struct node{
    int a , b , c , d ;
}p[N];

int ans , n ;

int main () {
    ios :: sync_with_stdio(false) ;
    cin.tie(0) , cout.tie(0) ;

    cin >> n ;

    for(int i=1; i<=n; i++) {
        cin >> p[i].a >> p[i].b >> p[i].c >> p[i].d ;
    }

    for(int cnt=1; cnt<=n; cnt++) {
        for(int i=n/4; ~i; i--) {
            for(int j=n/4; ~j; j--) {
                for(int k=n/4; ~k; k--) {
                    for(int l=n/4; ~l; l--) {
                        if(i)f[i][j][k][l] = max ( f[i-1][j][k][l] + p[cnt].a , f[i][j][k][l]) ;
                        if(j)f[i][j][k][l] = max ( f[i][j-1][k][l] + p[cnt].b , f[i][j][k][l]) ;
                        if(k)f[i][j][k][l] = max ( f[i][j][k-1][l] + p[cnt].c , f[i][j][k][l]) ;
                        if(l)f[i][j][k][l] = max ( f[i][j][k][l-1] + p[cnt].d , f[i][j][k][l]) ;
                }
            }
        }
    }
    }

    cout << f[n/4][n/4][n/4][n/4] ;

    return 0 ;
}

F

类型题：每个边有两个权值，在保证第一种边最小的情况下保证第二种边最小，可以先通过迪杰斯特拉跑第一种边建图，然后再跑一遍dijkstra；实际上不用真的把图建出来，用dist可以判断；该题第一种边权为1，因此可以bfs建图

#include<iostream>
#include<cstring>
#include<queue>
#define int long long

using namespace std ;

const int N = 1e5 + 10 , M = 2e5 + 10 , inf = 0x3f3f3f3f3f3f3f3f ;

typedef pair<int,int> pii ;

int n , m , idx , e[M*2] , w[M*2] , ne[M*2] , h[N] , dist[N] , cnt[N] ;
bool book[N] ;

void add(int a, int b, int c) {
    e[idx] = b , w[idx] = c , ne[idx] = h[a] , h[a] = idx ++ ;
}

//dij的核心是贪心。该题经过城市更少的条件优先级更高因此可以用优先队列维护从源点到还未确定最
//短距离的点的中转次数；然后借用cnt数组进行松弛；被注释掉的写法也可以过因为不可能出现当
//cnt[j] > cnt[now] + 1时dist[j] != inf（已验证）；因为按照贪心过程是按照中转次数从小
//到大更新的

int dij() {
    memset ( dist , 0x3f , sizeof dist ) ;
    memset ( cnt , 0x3f , sizeof cnt ) ;
    priority_queue<pii , vector<pii> , greater<pii>> q ;
    q.push({0,1}) ;
    dist[1] = 0 ;
    cnt[1] = 1 ;
    while(q.size()) {
        auto t = q.top() ;
        q.pop() ;
        int now = t.second ;
        if(book[now]) continue;
        book[now] = true ;
        for(int i=h[now]; ~i; i=ne[i]){
            int j = e[i] ;
//             if(cnt[j] >= cnt[now] + 1 ) {
//                 if(dist[j] > dist[now] + w[i]) {
//                     dist[j] = dist[now] + w[i] ;
//                     cnt[j] = cnt[now] + 1 ;
//                     q.push({cnt[j] , j}) ;
//                 }
//             }  
            if(cnt[j] > cnt[now] + 1 ) {
//            if(dist[j] == inf){
                cnt[j] = cnt[now] + 1 ;
                dist[j] = dist[now] + w[i] ;
                q.push({cnt[j] , j}) ;
            }
            else if(cnt[j] == cnt[now] + 1) {
                if(dist[j] > dist[now] + w[i]) {
                    dist[j] = dist[now] + w[i] ;
                }
            } 
        }
    }
    return dist[n] ;
}

//spfa的核心是bfs；注意区别在于在队列中的点依然可能被更新从而增加中转次数，已经入过队的同理
//因此如果只判断终点是否第一次到达不能保证路径中的每个点都是经过最小中转次数到达的，因此需要
//cnt数组
int spfa() {
    memset( dist , 0x3f , sizeof dist) ;
    memset( cnt , 0x3f , sizeof cnt) ;
    queue<int> q ;
    q.push(1) ;
    dist[1] = 0 ;
    cnt[1]  = 1 ;
    book[1] = true ;
    while(q.size()) {
        int t = q.front();
        q.pop() ;
        for(int i=h[t]; ~i; i=ne[i]) {
            int j = e[i] ;
            if(cnt[j] >= cnt[t] + 1 ) {
                if(dist[j] > dist[t] + w[i]) {
                    dist[j] = dist[t] + w[i] ;
                    cnt[j] = cnt[t] + 1 ;
                    if(!book[j]) {
                        book[j] = true ;
                        q.push(j) ;
                    }
                }
            }
            //          if(dist[j] > dist[t] + w[i]) {
            //              int temp = cnt[j] ;
            //              cnt[j] = cnt[t] + 1 ;
            //                 dist[j] = dist[t] + w[i] ;
            //              if(!book[j]) {
            //                  book[j] = true ;
            //                  q.push(j) ;
            //              }
            //          }
        }
    }
    return dist[n] ;
}

signed main () {
    ios :: sync_with_stdio(false) ;
    cin.tie(0) , cout.tie(0) ;

    memset( h , -1 , sizeof h) ;

    cin >> n >> m ;

    while( m -- ) {
        int a , b , c ; 
        cin >> a >> b >> c ;
        add (a , b , c) ;
        add (b , a , c) ;
    }

    int res = dij() ;

    cout << cnt[n] << ' ' << res ;

    return 0 ;
}