A. Accumulation of Dominoes

這題了一個構(gòu)造矩陣的方法。相鄰的兩個方塊組在一起是一張牌，問有多少張牌是兩個數(shù)的差值為一的。

根據(jù)構(gòu)造規(guī)則發(fā)現(xiàn)只有兩個方塊在一行才可能差值唯一，除非矩陣的寬只有一

#include<bits/stdc++.h>
#define int long long
using namespace std;

int32_t main() {
    int n , m;
    cin >> n >> m;
    if( m == 1 )	cout << n - 1 << "
";
    else	cout << n * m - n;
    return 0;
}

B. Basketball Together

一個隊伍中每個人都價值可以轉(zhuǎn)變成隊伍中價值最高的價值。所以把所有人排序，然后選一個價值高，然后一直選擇價值低的直到隊伍的價值大于D

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e5+5;
int p[N];

int read() {
    int x = 0, f = 1, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

int32_t main() {
    int n = read() , d = read() , res = 0;
    for( int i = 1 ; i <= n ; i ++ ) p[i] = read();
    sort( p + 1 , p + 1 + n , greater<int>() );
    for( int i = 1 , j = n , k; i <= j ; i ++ ){
        k = 1;
        while( i < j && p[i] * k <= d ) k ++ , j --;
        if( p[i] * k > d ) res ++;
    }
    cout << res << "
";
    return 0;
}

G. Garage

設正方形的邊長為(c),則正方形的面積為(c^2=b^2-a^2)

因為(b>a)，當(b=a+1)時，可得(c^2=b^2-a^2=2a+1)，此時包含了所有大于三的奇數(shù)

當(b=a+2)時，可得(c^2=b^2-a^2=4a+4)，此時包含了所有大于等于 8 所有 4 的倍數(shù)

對于其他情況可以驗證一定被這兩種情況給包含，說有我們可以二分(c)，然后計算出c是第幾大的。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int32_t main() {
    int n;
    cin >> n;
    int l = 3 , r = INT_MAX , mid , res;
    while( l <= r ){
        mid = ( l + r ) >> 1;
        if( ( mid - 1 ) / 2 + max( 0ll , mid / 4 - 1 ) >= n ) res = mid , r = mid - 1;
        else l = mid + 1;
    }
    cout << res << "
";
    return 0;
}

M. Moving Both Hands

首先在圖中加入((u,v))的反向邊((v,u)’)，用(d(x,y))表示從x 到 y 的最短路徑，那么令中間點為(k)，那么題目要求的就是(d(1,k)+d(p,k))，然后用反向邊表示(d(1,k)+d’(k,p))

然后再圖中對于每一個點(x)都加入一個點(x’),這樣在加入((u,v,w))的時候同時加入一個((v’,u’,w))，這樣題目所求就變成了(d(1,k)+d(k’,p’))。然后整個圖中只能從正向點走向方向點一次，所以在圖中再加入((x,x’,0))

這樣所求就變成了(d(1,k)+d(k,k’)+d(k’,p’)=d(1,p’))，從1 跑一遍 dijkstra，然后輸出就好了

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 4e5+5;
int n , m , dis[N];
bitset<N> vis;

vector< pair<int,int> > e[N];

int read() {
    int x = 0, f = 1, ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '-') ch = getchar();
    if (ch == '-') f = -1, ch = getchar();
    while (ch >= '0' && ch <= '9') x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
    return x * f;
}

void dij(){
    fill( dis , dis + N , 1e18 );
    dis[1] = 0;
    priority_queue< pair<int,int> , vector<pair<int,int>> , greater<pair<int,int>> > q;
    q.push( { 0 , 1 } );
    while( q.size() ){
        int u = q.top().second ; q.pop();
        if( vis[u] ) continue;
        vis[u] = 1;
        for( auto [ v , w ] : e[u] )
            if(  dis[v] > dis[u] + w ){
                dis[v] = dis[u] + w;
                q.push( { dis[v] , v } );
            }
    }
}

int32_t main() {
    n = read() , m = read();
    for( int u , v , w ; m ; m -- ){
        u = read() , v = read() , w = read();
        e[u].push_back( { v , w } ) , e[ v+n ].push_back( { u+n , w } );
    }
    for( int i = 1 ; i <= n ; i ++ ) e[i].push_back({ i+n , 0 } ) ;
    dij();
    for( int i = 2 ; i <= n ; i ++ )
        cout << ( dis[i+n] != 1e18 ? dis[i+n] : -1ll ) << " ";
}