A. Accumulation of Dominoes

这题了一个构造矩阵的方法。相邻的两个方块组在一起是一张牌，问有多少张牌是两个数的差值为一的。

根据构造规则发现只有两个方块在一行才可能差值唯一，除非矩阵的宽只有一

#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

一个队伍中每个人都价值可以转变成队伍中价值最高的价值。所以把所有人排序，然后选一个价值高，然后一直选择价值低的直到队伍的价值大于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)，此时包含了所有大于三的奇数

当(b=a+2)时，可得(c^2=b^2-a^2=4a+4)，此时包含了所有大于等于 8 所有 4 的倍数

对于其他情况可以验证一定被这两种情况给包含，说有我们可以二分(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 ) << " ";
}