2024 ccpc 东北四省补题

待补：B,C,F,G,H,M,K
补题链接：https://codeforces.com/gym/105173/my

J.Breakfast

签到，甚至保证了两个输入和输出。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
#define int long long 
using namespace std ;
int T = 1 ;
int n, m, k ;
void solve(){
    cin >> n >> m ;
    double ans = n * 0.6 + m ;
    // cout << ans << endl ;
    printf("%.2lf\n",ans) ;
}
signed main(){
    // cin >> T ;
    while(T --){
        solve() ;
    }
}

---

A.Paper Watering

我们可以先把所有开根号能算到的数算出来，然后从大到小排序，接着我们一起来算所有这些数的平方方向能算到的数，但如果出现前一个数是当前数的平方或者当前数是 $1$ 直接跳过，其他则直接加上还剩余的能走的步数即可。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
#define int long long
#define PII pair<int, int> 
#define IPII pair<int, PII> 
#define PI acos(-1)
using namespace std;
const int N = 1e6 + 10 ;
const int M = 1020 ;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353 ;//全一才位1
const double eps = 1e-9 ;
int gcd(int a, int b){ return b == 0 ? a : gcd(b, a%b); }
int lcm(int a, int b){ return a * b / gcd(a,b); } 
int qmi(int a, int b){
    int res = 1 ;
    while(b){
        if(b&1) res = (res * a) % mod ;
        b >>= 1 ;
        a = (a * a) % mod ;
    }
    return res ;
}
int T = 1 ;
int n , m, k ;
void solve() {
    cin >> n >> k ;
    vector<int> vec ;
    int t = n ;
    vec.push_back(n) ;
    if(n== 1){
        cout << 1 << endl ;
        return ;
    }
    int ans = k + 1 ;
    int num = k ;
    int t2 = n ;

    for(int i = 1 ; i <= k ; ++ i){
        t = (int)sqrt(t) ;
        ans ++ ;
        vec.push_back(t) ;
        if(t == 1) break ;
    }
//    cout << ans << endl ;
    for(int i = 1 ; i < vec.size() ; ++ i){
        num = k - i ;//表示能往前走的步数
        t2 = vec[i] ;
        if(vec[i-1]  == vec[i] * vec[i] || t2 == 1) continue ;
        ans += num ;

//        cout << num << endl ;
    }
    cout << ans << endl ;
}
signed main(){
    IOS ;
//    cin >> T ;
    while(T --){
        solve() ;
    }
    return 0;
}

 

 

---

D.nIM gAME

如果要赢那么所选的数字之和一定是偶数，但我们可以发现后手总有办法破坏奇偶性，所以说先手一定必输。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
#define int long long 
using namespace std ;
int T = 1 ;
int n, m, k ;
string s1 = "lose" ;
string s2 = "win" ;
void solve(){
    cin >> n ;
    cout << s1 << endl ;
}
signed main(){
    cin >> T ;
    while(T --){
        solve() ;
    }
}

 

---

E.Checksum

我们记 $A$ 中 $1$ 的数目是 $n_1$，$B$ 中 $1$ 的数目是 $n_2$，又因为保留 $k$ 位二进制,我们要找的 $B$ 符合这个等式

所以我们可以枚举 $B$ 的二进制串中 $1$ 的数目，判断 $(n1 + n2 )\ \%\ 2^k$ 的二进制串能否通过 $n2$ 个 $1$ 构造出来， 也就是 $(n1 + n2 )\ \%\ 2^k$ 中 $1$ 的数目是否等于我们枚举的数量。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
#define int long long
#define PII pair<int, int> 
#define IPII pair<int, PII> 
#define PI acos(-1)
using namespace std;
const int N = 1e6 + 10 ;
const int M = 1020 ;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353 ;//全一才位1
const double eps = 1e-9 ;
int gcd(int a, int b){ return b == 0 ? a : gcd(b, a%b); }
int lcm(int a, int b){ return a * b / gcd(a,b); } 
int qmi(int a, int b){
    int res = 1 ;
    while(b){
        if(b&1) res = (res * a) % mod ;
        b >>= 1 ;
        a = (a * a) % mod ;
    }
    return res ;
}
int T = 1 ;
int n , m, k ;
string s ;
int clac(int x){
    int num = 0 ;
    while(x){
        num ++ ;
        x -= x&-x ;
    }
    return num ;
}
void solve() {
    cin >> n >> k ;
    cin >> s ;
    int num = 0 ;
    int ans = INF ;
    for(int i = 0 ; i < s.size() ; ++ i){
        num += (s[i] == '1') ;
    }
    for(int i = 0 ;  i <= k ; ++ i){
        int num2 = num + i ;//表示是否能用i表示出nunm2
        int te = num2 ;
        if(clac(num2 % (1LL << k)) == i){
            ans = min(ans,num2 % (1LL << k)) ;
        }
    }
    vector<int> vec ;
    if(ans != INF){
        for(int i = k - 1 ; i >= 0 ; -- i){
            if(ans >> i &1){
                cout << 1 ;
            }else{
                cout << 0 ;
            }
        }
        cout << endl ;
    }else{
        cout << "None" << endl ;
    }
}
signed main(){
    IOS ;
    cin >> T ;
    while(T --){
        solve() ;
    }
    return 0;
}

 

---

I. Password

我们设 $dp[i]$ 表示的是最后一个排列在 $i$ 位置结束时的方案数（其实也就是保证最后 $k$ 个数一定是一个排列），那么 $dp[n]$ 就是我们想要的答案，

我们在 $dp[i]$ 后接上 $j$ 个数，由于很显然 $[1,k]$ 和 $[n-k+1,n]$ 都一定是一个全排列，那么对于 $dp[i]$ 来说，$[i-k+1,i]$ 一定是一个全排列，在加上 $j$ 个数后 $[i+j-k+1,i+j]$ 也一定是一个全排列。

如果不过考破坏性质的话，我们就不是乘上 $g[j]$ ，而是乘上 $j!$ ，但是这样是会导致破坏原有排列最后一位数的位置。

这里我们来说明 $g[j]$ 的定义

• 在某个完整的排列 $i$ 后接上 $j$ 个数并且不破坏原来性质（也就是前一个排列的最后一位还是 $i$ ,不能）的方案数。

比如说对于序列（其结尾位置为$i$） $1,2,3,4,5$ ，我们要在后续接上 $3$ 个数，那么 $4,5,x,x,x$ 一定是一个排列，但同时我们要保证 $3,4,5,x,x$ 和 $2,3,4,5,x$ 一定不是一个排列，否则就会破坏前一个完整的排列的最后一个数的位置。

计算 $g[j]$ 也就可以看作从 $j!$ 中减去不合法的方案数，我们可以枚举每一个位置把其合法的情况减去（为了减少重复计算）。

先考虑最后一个位置不合法，也就是 $k + j - 1$ 这个位置不合法，如果假设其合法说明 $[j,k + j - 1]$是一个完整排列也就有 $(j-1)!$种情况，而对于 $[k+j-1,k+j]$，由于我们确定了 $k + j - 1$ 这个位置不合法，我们也就要保证 $[k+j-1,k+j]$ 其都不合法。

我们对于 $[1,i]$这一部分就是 $i!$ 种填法，而 $[i+1,j]$ 这部分，为了保证其都不合法，也就是说任意 $i < p < j$，这一段不能是 $i + 1, \dots p$ 这些数任意排列的结果，我么可以发现这正好可以看作在$i+1$ 这个排列后接上 $j-i$ 个数，也就是 $g[j-i]$ ，所以枚举的每一个位置 $j$ 的合法方案就是 $i! * g[j-i]$。

#include <bits/stdc++.h>
#define IOS                  ios::sync_with_stdio(0); cin.tie(0);cout.tie(0)
#define endl '\n'
#define int long long
#define PII pair<int, int>
#define IPII pair<int, PII>
#define PI acos(-1)
using namespace std;
const int N = 1e5 + 10;
const int M = 1020;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 998244353; // 全一才位1
const double eps = 1e-9;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int lcm(int a, int b) { return a * b / gcd(a, b); }
int qmi(int a, int b)
{
    int res = 1;
    while (b)
    {
        if (b & 1)
            res = (res * a) % MOD;
        b >>= 1;
        a = (a * a) % MOD;
    }
    return res;
}
int T = 1;
int ans = 0 ;
int n, m, k;
int s[N] ;
int dp[N] ;
int g[N] ;
int fac[N] ;
void solve()
{
    cin >> n >> k;
    if(k > n){
        cout << 0 << endl ;
        return ;
    }
    g[1] = 1 ;
    for(int i = 2; i <= k ; ++ i){
        g[i] = fac[i] ;
        for(int j = 1 ; j <= i - 1 ; ++ j){
            g[i] = (g[i] - fac[j] * g[i-j] % MOD + MOD) % MOD ;
        }
    }
    dp[k] = fac[k] ;
    for(int i = k + 1 ; i <= n ; ++ i){
        for(int j = 1; j <= k ; ++ j){
            dp[i] = (dp[i] + dp[i-j] * g[j] % MOD + MOD) % MOD  ;
        }
    }
    cout << dp[n] << endl ;
}
signed main()
{
    IOS;
    fac[1] = 1 ;
    for(int i = 2 ; i <= N ; ++ i) fac[i] = fac[i-1] * i % MOD ;
    while (T--)
    {
        solve();
    }
    return 0;
}

 

---

L. Bracket Generation

我们可以发现第二种操作只要在其括号里的都放好后就可以进行了，也不一定就要马上进， 比如 $(()_1()_2)()_3$ 我们在放好第二个括号对后就可以进行操作 $2$ 了，但我们也同样可以在放好第三个括号对后进行操作 $2$ 。我们由此就可以构造出一个操作的序列，如果是第一种操作生成的括号对就记为 $1$ ，反之记为 $2$ ，比如说第二个样例 $((()())()())(())$ 生成的操作序列就是 $1 1 2 1 1 2 1 2$ 。也就相当于可以把 $2$ 插入到之后的任意一个位置，第一个 $2$ 有 $6$ 种的情况，第二个 $2$ 有 $3$ 种的情况，第三个 $2$ 有 $1$ 种的情况，最后算一个乘积就行了。

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define endl '\n'
#define int long long
#define PII pair<int, int> 
#define _rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define _per(i,a,b) for( int i=(a); i>=(b); --i)
using namespace std;
const int N = 1e6+10 ;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 998244353   ;
const double eps = 1e-9 ;
int gcd(int a, int b){ return b == 0 ? a : gcd(b, a%b); }
int lcm(int a, int b){ return a * b / gcd(a,b); } 
int qmi(int a, int b){
    int res = 1 ;
    while(b){
        if(b&1) res = a * res % MOD ;
        b >>= 1 ;
        a = a * a % MOD ;
    }
    return res ;
}
int T = 1 ;
int ans = 0 ;
int n , m, k, q ;
string s ;
void solve(){
    // cin >> n ;
    cin >> s ;
    vector<char> vec ;
    vector<int> vec2 ;
    for(int i = 0 ; i < s.size() ; ++ i){
        if(vec.empty() || s[i] == '('){
            vec.push_back(s[i]) ;
        }else{
            vec.pop_back() ;
            if(s[i-1] =='('){
                vec2.push_back(1) ;
            }else{
                vec2.push_back(2) ;
            }
        }
    }
    ans = 1 ;
    for(int i = 0 ; i < vec2.size() ; ++ i){
        cout << vec2[i] << " " ;
        if(vec2[i] == 2){
            ans = (ans * (vec2.size() - i)) % MOD ;
        }
    }
    cout << endl ;
    cout << ans << endl ;
}
signed main(){
    IOS ;
    // cin >> T ;
    while(T --){
        solve() ;
    }
    return 0;

}

---

 

M.House

暴力模拟，我们先枚举边 $DC$ ，然后再枚举其他点 $F$ 与这条边的关系，分为在其上侧还是下侧，又分为该点是否可以当作三角形的顶点，也就是到 $D$ 和 $C$ 的距离是否都相等。还有与 $D$ 或 $C$ 与 $F$ 连接起来的线是否与 $DC$ 垂直，如果垂直就分别记录一下垂直的 $FD$ 或 $FC$ 的长度。然后分为上下两侧分别计算累加就行了。

#include <bits/stdc++.h>
#define IOS  ios::sync_with_stdio(0); cin.tie(0);cout.tie(0)
#define endl '\n'
#define  int long long
#define _rep(i,a,b) for( int i=(a); i<=(b); ++i)
#define _per(i,a,b) for( int i=(a); i>=(b); --i)
#define PII pair<int, int>
#define IPII pair<int, PII>
#define PI acos(-1)
using namespace std;
const int N = 310;
const int M = 2020;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7; // 全一才位1
const double eps = 1e-9;
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
int lcm(int a, int b) { return a * b / gcd(a, b); }
int qmi(int a, int b){
    int res = 1;
    while (b){
        if (b & 1)
            res = (res * a) % MOD; 
        b >>= 1;
        a = (a * a) % MOD;
    }
    return res;
}
int ans ; 
int T = 1;
int n, m, k;
PII a[N] ;
vector<PII> vec[N] ;
int check(int k, int i,int j){//k在ij的位置
    PII ik = {a[k].first - a[i].first ,a[k].second - a[i].second} ;
    PII jk = {a[k].first - a[j].first ,a[k].second - a[j].second} ; 
    return ik.first * jk.second - ik.second * jk.first ;
}
int dis(int i, int j){
    PII x = a[i], y = a[j] ;
    return (x.first - y.first) * (x.first - y.first) + (x.second - y.second) * (x.second - y.second) ;
}
bool right(int k, int i, int j){//ij 和 ki 是否组成直角
    PII ik = {a[k].first - a[i].first ,a[k].second - a[i].second} ;
    PII ij = {a[j].first - a[i].first ,a[j].second - a[i].second} ; 
    return ik.first * ij.first + ik.second * ij.second == 0 ;
}
void solve(){
    cin >> n ;
    int x, y ;
    for(int i = 1 ; i <= n ; ++ i){
        cin >> x >> y ;
        a[i] = {x, y} ;
    }
    for(int i = 1; i <= n ; ++ i){
        for(int j = i + 1 ; j <= n ; ++ j){//枚举dc
            vector<int> vec1 ;//表示可以当作三角形顶点的点，在dc上侧
            vector<int> vec2 ;//表示可以当作三角形顶点的点，在dc下侧
            map<int,int> mp1 ; //上侧一边长度为first的数目
            map<int,int> mp2 ;//上侧另一边长度为first的数目
            map<int,int> mp3 ; //下侧一边长度为first的数目
            map<int,int> mp4 ;//下侧另一边长度为first的数目
            for(int k = 1 ; k <= n ; ++ k){
                if(k == i || k == j) continue ;
                if(check(k,i,j) < 0){//在上侧
                    if(dis(k,i) == dis(k,j)){
                        vec1.push_back(k) ;
                    }
                    if(right(k,i,j)){

                        mp1[dis(i,k)] ++ ;
                    }
                    if(right(k,j,i)){

                        mp2[dis(j,k)] ++ ;
                    }
                }else if(check(k,i,j) > 0){//在下侧
                    if(dis(k,i) == dis(k,j)){
                        vec2.push_back(k) ;
                    }
                    if(right(k,i,j)){
                        mp3[dis(i,k)] ++ ;
                    }
                    if(right(k,j,i)){
                        mp4[dis(j,k)] ++ ;
                    }
                }
            }

            int num = 0 ;
            for(auto e : mp3){
                if(mp4.count(e.first)){
                    num += e.second * mp4[e.first] ;
                }
            }
            ans += vec1.size() * num ;
            num = 0 ;
            for(auto e : mp1){
                if(mp2.count(e.first)){
                    num += e.second * mp2[e.first] ;
                }
            }
            ans += vec2.size() * num ;
        }
    }
    cout << ans << endl ;
}
signed main(){
    IOS;
    while (T--){
        solve();
    }
    return 0;
}