C. Darkness I
首先根据短边放一条对角线,然后往后每隔一列只放一个即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n, m;
cin >> n >> m;
cout << (n + m + 1) / 2;
return 0;
}
H. Binary Craziness
因为是树的关系,度数的种类并不会太多,直接枚举度数就好了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int32_t main(){
ios::sync_with_stdio(false) , cin.tie(nullptr) , cout.tie(nullptr);
int n , m ;
cin >> n >> m;
vector<int> deg( n + 1 );
for( int x , y ; m ; m -- ){
cin >> x >> y;
deg[x] ++ , deg[y] ++;
}
unordered_map<int,int> cnt;
for( int i = 1 ; i <= n ; i ++ )
cnt[ deg[i] ] ++;
int res = 0;
vector<int> a , b;
for( const auto &[ x , y ] : cnt ) a.push_back(x) , b.push_back(y);
for( int i = 0 ; i < a.size() ; i ++ )
for( int j = i+1 ; j < a.size() ; j ++ ){
(res += (a[i] ^ a[j])*(a[i] | a[j])%mod*(a[i] & a[j])%mod*b[i]%mod*b[j]%mod)%=mod;
}
cout << res <<"\n";
return 0;
}
I. Step
首先\(lcm(p_1,\cdots,p_n)\)的倍数天一定可以回到\(1\)。前\(i\)天累计移动\(\frac{i(i+1)}{2}\)步,所以要寻找最小的\(i\)满足\(\frac{i(i+1)}{2} = k\times lcm\)
可以变形为\(i(i+1)=k(2lcm)\),把\(2lcm\)进行质因数分解,可以估算出质因子的数目不超过20 个,因为相邻数互质,每一个数只能属于\(i\)或\(i+1\)中的一个。所以可以通过二进制枚举的形式,设属于\(i\)的质因子乘积为\(y\),属于\(i+1\)的质因子乘积为\(x\)。同理也可以吧\(k\)质因数分解,然后分给\(i+1\)乘积为\(a\),分给\(i\)的乘积是\(b\)。所以可以得到\(ax-by=1\),用扩展欧几里得借一下方程就好了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int power( int x , int y ){
int ans = 1;
while( y ){
if( y & 1 ) ans = ans * x;
y >>= 1 , x = x * x;
}
return ans;
}
int exgcd( int a , int b , int & x , int & y ){
if( b == 0 ) { x = 1 , y = 0 ; return a;}
int d = exgcd( b , a%b , x , y );
int z = x ; x = y ; y = z - y * (a / b);
return d;
}
int32_t main(){
ios::sync_with_stdio(false) , cin.tie(nullptr) , cout.tie(nullptr);
int n;
cin >> n;
unordered_map<int,int> prime;
for( int i = 1 , x ; i <= n ; i ++ ){
cin >> x;
for( int j = 2 , cnt ; j*j <= x; j ++ ){
if( x % j == 0 ){
cnt = 0;
while( x % j == 0 ) x /= j , cnt ++;
prime[j] = max( prime[j] , cnt );
}
}
if( x > 1 ) prime[x] = max( prime[x] , 1ll );
}
vector<int> a;
prime[2] ++;
for( const auto & [ x , y ] : prime )
a.push_back( power( x , y ) );
int res = LLONG_MAX;
for( int i = 0 , m = (1ll<<a.size())-1 , x , y , t ; i <= m ; i ++ ){
x = y = 1 , t = i;
for( int j = 0 ; j < a.size() ; j ++ , t >>= 1){
if( t & 1 ) x *= a[j];
else y *= a[j];
}
int kx , ky , d ;
d = exgcd( x , -y , kx , ky );
if( kx && ky && d ) res = min( res , ky * y) ;
}
cout << res;
return 0;
}
F. Inverse Manacher
找到枚举|
的位置,如果f[i]=1
所有左右两侧的字母不同。固定第一个字母,然后根据这个规律构造即可
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n, m;
cin >> n, m = n * 2 + 2;
vector<int> a(m+1);
for( int i = 1 ; i <= m ; i ++ ) cin >> a[i];
cout << "a";
for( int i = 4 , t = 0 ; i < m ; i += 2 ){
if( a[i] == 1 ) t ^= 1;
cout << "ab"[t];
}
return 0;
}
J. Expansion
贪心吧。维护一下前缀和中的最大值,如果过不去了就在最大值处多停留几次。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int n, res = 0;
cin >> n;
for (int i = 1, x, sum = 0, large = 0, cnt = 0, p; i <= n; i++) {
cin >> x;
sum += x;
if (sum < 0 && (i == n || i == 1)) {
cout << "-1\n";
return 0;
}
large = max(large, sum);
if (cnt + sum >= 0) {
res++;
cnt += sum;
} else {
p = -cnt - sum;
if (large == 0) {
cout << "-1\n";
return 0;
}
p = (p + large - 1) / large;
cnt += large * p + sum;
res += p + 1;
}
}
cout << res;
return 0;
}
K. Dice Game
对于\([2,n+1]\)号人对游戏的贡献是相同的,所以单独考虑即可。如果1号要输,则必须输给所有的人。
对于1号,当他固定投出\(i\)的时候,2 号和他平局的概率是\(\frac{1}{m}\),2 号获胜的概率是\(\frac{m-i}{m}\),所以2号在第\(x\)局获胜的概率是\(\frac{m-i}{m^x}\),所以2 号获胜的概率是\(\sum_{x=1}^{+\infty}\frac{m-i}{m^x}=\frac{m-x}{m-1}\)。所以\(n\)个人获胜的概率是\((\frac{m-i}{m-1})^n\)。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int power( int x , int y ){
int ans = 1;
while( y ){
if( y & 1 ) ans = ans * x % mod;
y >>= 1 , x = x * x % mod;
}
return ans;
}
int inv( int x ){
return power( x , mod - 2 );
}
int32_t main(){
ios::sync_with_stdio(false) , cin.tie(nullptr) , cout.tie(nullptr);
int n , m ;
cin >> n >> m;
int invs = inv( m-1 );
for( int i = 1 ; i <= m ; i ++ ){
cout << power((m-i) * invs%mod , n ) << " ";
}
return 0;
}
M. Different Billing
鸡兔同笼?枚举一下就好了。
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int x , y;
cin >> x >> y;
for( int a , b = 0 , c ; b <= x ; b ++ ){
c = y - b * 1000;
if( c % 2500 ) continue;
c /= 2500 , a = x - b - c;
if( a < 0 || c < 0 ) continue;
cout << a << " " << b << " " << c;
return 0;
}
cout << "-1\n";
return 0;
}
- Programming Collegiate Provincial Contest Hubeiprogramming collegiate provincial contest programming collegiate provincial shandong programming provincial collegiate sichuan programming collegiate provincial guangdong programming provincial collegiate shandong programming collegiate provincial counting programming provincial collegiate sponsored 2023 programming collegiate provincial 题解programming collegiate provincial programming collegiate jiangsu contest