《Codeforces Round #742 (Div. 2)》

2023-11-22 08:39:40

A：水题

《Codeforces Round #742 (Div. 2)》
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tu;
const int N = 1e6 + 5;
const int M = 1e3 + 5;
const double eps = 1e-10;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read() {
    int f = 1;int x = 0;char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
inline long long ADD(long long x,long long y) {return (x + y) % Mod;}
inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;}
inline long long MUL(long long x,long long y) {return x * y % Mod;}

void solve() {
    int n;n = read();
    string s;cin >> s;
    
    string ans = "";
    for(int i = 0;i < s.size();++i) {
        if(s[i] == 'U') ans += "D";
        else if(s[i] == 'D') ans += 'U';
        else if(s[i] == 'L') ans += "LR";
    }
    cout << ans << "\n";
} 
int main() {    
    int ca;ca = read();
    while(ca--) {
        solve();
    }
    //system("pause");
    return 0;
}
View Code

B：维护一下二进制位即可。

《Codeforces Round #742 (Div. 2)》
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tu;
const int N = 3e5 + 5;
const int M = 1e3 + 5;
const double eps = 1e-10;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read() {
    int f = 1;int x = 0;char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
inline long long ADD(long long x,long long y) {return (x + y) % Mod;}
inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;}
inline long long MUL(long long x,long long y) {return x * y % Mod;}

int pre[N];
void init() {
    pre[0] = 0;
    for(int i = 1;i < N;++i) pre[i] = pre[i - 1] ^ i;
}
void solve() {
    int a,b;a = read(),b = read();
    int ma = pre[a - 1],ans = a;
    if(ma == b) printf("%d\n",ans);
    else {
        int tmp = 0;
        for(int i = 29;i >= 0;--i) {
            int g = (ma >> i) & 1;
            int g2 = (b >> i) & 1;
            if(g ^ g2 == 1) tmp += (1 << i);
        }
        if(tmp != a) printf("%d\n",ans + 1);
        else printf("%d\n",ans + 2);
    }
    
} 
int main() {    
    init();
    int ca;ca = read();
    while(ca--) {
        solve();
    }
    //system("pause");
    return 0;
}
View Code

C：这题质量其实挺高的。

因为第i位如果不从当前位相加得到，那么最多可以从i - 2的位置借1个值。

那么可以发现状态并不是很多。

记忆化dfs即可。

《Codeforces Round #742 (Div. 2)》
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tu;
const int N = 3e5 + 5;
const int M = 1e3 + 5;
const double eps = 1e-10;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read() {
    int f = 1;int x = 0;char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
inline long long ADD(long long x,long long y) {return (x + y) % Mod;}
inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;}
inline long long MUL(long long x,long long y) {return x * y % Mod;}

LL dp[15][2][2][2][2];
string s;
bool check(int x,int y) {
    if(x <= 8 && y == x + 1) return true;
    else return false;
}
LL dfs(int len,bool ned1,bool ned2,bool limit1,bool limit2) {
    if(len == s.size()) {
        if(limit2 || limit1) return 0;
        if(!ned1 && !ned2) return 1;
        else return 0;
    }
    if(dp[len][ned1][ned2][limit1][limit2] != -1) return dp[len][ned1][ned2][limit1][limit2];
    int now = s[len] - '0';
    LL ans = 0;
    for(int i = 0;i <= 9;++i) {
        for(int j = 0;j <= 9;++j) {
            int x = i + j,y = (i + j) % 10;
            if(ned1) {
                if(x >= 10) {
                    if(y == now) ans += dfs(len + 1,ned2,false,limit1 & (i == 0),limit2 & (j == 0));
                    else if(check(y,now)) ans += dfs(len + 1,ned2,true,limit1 & (i == 0),limit2 & (j == 0));
                }
                else if(x == 9 && now == 0) ans += dfs(len + 1,ned2,true,limit1 & (i == 0),limit2 & (j == 0));
            }
            else {
                if(x <= 8) {
                    if(y == now) ans += dfs(len + 1,ned2,false,limit1 & (i == 0),limit2 & (j == 0));
                    else if(y == now - 1) ans += dfs(len + 1,ned2,true,limit1 & (i == 0),limit2 & (j == 0));
                }
                else if(x == 9 && y == now) ans += dfs(len + 1,ned2,false,limit1 & (i == 0),limit2 & (j == 0));
            }
        }
    }
   // if(ans != 0) printf("len is %d ned1 is %d ned2 is %d ans is %d\n",len,ned1,ned2,ans);
    return dp[len][ned1][ned2][limit1][limit2] = ans;
}
void solve() {
    memset(dp,-1,sizeof(dp));    
    cin >> s;
    LL ans = dfs(0,false,false,true,true);
    printf("%lld\n",ans);
} 
int main() {    
    int ca;ca = read();
    while(ca--) {
        solve();
    }
   // system("pause");
    return 0;
}
View Code

D：比C题还水感觉。

显然要让答案最大，我们要维护的最高位出现的次数尽可能多。

所以考虑从最高位开始取。这个对于取的循环，从小到大还是从大到小会不一样。

我们考虑从小到大，因为这样能保证后面的最高位也尽可能多。

即对于100 3  得80 + 10 + 10//从小到大、

得90 5 5.//从大到小。

《Codeforces Round #742 (Div. 2)》
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tu;
const int N = 1e6 + 5;
const int M = 2e4 + 5;
const double eps = 1e-10;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read() {
    int f = 1;int x = 0;char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
inline long long ADD(long long x,long long y) {return (x + y) % Mod;}
inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;}
inline long long MUL(long long x,long long y) {return x * y % Mod;}

int a[15],pw[15],ans[105];
void solve() { 
    pw[0] = 1;
    for(int i = 1;i <= 9;++i) pw[i] = pw[i - 1] * 10;
    int ca;ca = read();
    while(ca--) {
        int s,n;s = read(),n = read();
        memset(ans,0,sizeof(ans));
        for(int i = 1;i <= n;++i) {
            int len = 0;
            int x = s;
            while(x) {
                a[++len] = x % 10;
                x /= 10;
            }
            int g = n - i;
            for(int k = len;k >= 1;--k) {
                if(ans[i] != 0) break;
                for(int j = 1;j <= 9;++j) {
                    LL ss = s - 1LL * j * pw[k - 1];
                    if(ss >= g) {
                       // printf("ss is %d g is %d pw[%d] is %d\n",ss,g,k - 1,pw[k - 1]); 
                        ans[i] = j * pw[k - 1];
                        s -= j * pw[k - 1];
                        break;
                    } 
                }
            }
        }
        if(s != 0) ans[1] += s;
        for(int i = 1;i <= n;++i) printf("%d%c",ans[i],i == n ? '\n' : ' ');

    }

} 
int main() {    
    solve();
    //system("pause");
    return 0;
}
View Code

E：这题感觉也挺简单的。

线段树上维护一下左右的最大长度和左右的值即可。

能连起来就合并一下答案。

有一个细节就是query的时候可能有需要合并的答案需要我们手动去合并。

《Codeforces Round #742 (Div. 2)》
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tu;
const int N = 2e5 + 5;
const int M = 2e4 + 5;
const double eps = 1e-10;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read() {
    int f = 1;int x = 0;char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
inline long long ADD(long long x,long long y) {return (x + y) % Mod;}
inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;}
inline long long MUL(long long x,long long y) {return x * y % Mod;}

int a[N];
struct Node{int L,r,Lmx,rmx,Lnum,rnum;LL sum;}node[N << 2];
LL cal(int x) {
    return 1LL * x * (x + 1) / 2;
}
void Pushup(int idx) {
    node[idx].Lnum = node[idx << 1].Lnum;
    node[idx].rnum = node[idx << 1 | 1].rnum;
    node[idx].sum = node[idx << 1].sum + node[idx << 1 | 1].sum;
    //printf("Lnum is %d rnum is %d\n",node[idx].Lnum,node[idx].rnum);
    if(node[idx << 1].rnum <= node[idx << 1 | 1].Lnum) {
        if(node[idx << 1].Lmx == node[idx << 1].r - node[idx << 1].L + 1) {
            node[idx].Lmx = node[idx << 1].Lmx + node[idx << 1 | 1].Lmx;
        }
        else node[idx].Lmx = node[idx << 1].Lmx;
        if(node[idx << 1 | 1].rmx == node[idx << 1 | 1].r - node[idx << 1 | 1].L + 1) {
            node[idx].rmx = node[idx << 1 | 1].rmx + node[idx << 1].rmx;
        }
        else node[idx].rmx = node[idx << 1 | 1].rmx;  
        node[idx].sum += cal(node[idx << 1].rmx + node[idx << 1 | 1].Lmx);
        node[idx].sum -= cal(node[idx << 1].rmx);
        node[idx].sum -= cal(node[idx << 1 | 1].Lmx);
    }
    else {
        node[idx].Lmx = node[idx << 1].Lmx;
        node[idx].rmx = node[idx << 1 | 1].rmx;
    }
}
void build(int L,int r,int idx) {
    node[idx].L = L,node[idx].r = r;
    if(L == r) {
        node[idx].sum = 1;
        node[idx].Lmx = node[idx].rmx = 1;
        node[idx].Lnum = node[idx].rnum = a[L];
        return ;
    }
    int mid = (L + r) >> 1;
    build(L,mid,idx << 1);
    build(mid + 1,r,idx << 1 | 1);
    Pushup(idx);
}
void update(int x,int val,int idx) {
    if(node[idx].L == node[idx].r) {
        node[idx].Lnum = node[idx].rnum = val;
        return ;
    }
    int mid = (node[idx].L + node[idx].r) >> 1;
    if(mid >= x) update(x,val,idx << 1);
    else update(x,val,idx << 1 | 1);
    Pushup(idx);
}
LL query(int L,int r,int idx) {
    if(node[idx].L >= L && node[idx].r <= r) return node[idx].sum;
    int mid = (node[idx].L + node[idx].r) >> 1;
    LL ans = 0;
    if(mid >= L) ans += query(L,r,idx << 1);
    if(mid < r) ans += query(L,r,idx << 1 | 1);
    if(mid >= L && mid < r && node[idx << 1].rnum <= node[idx << 1 | 1].Lnum) {
        int ld,rd;
        if(node[idx << 1].r - node[idx << 1].rmx + 1 >= L) ld = node[idx << 1].rmx;
        else ld = node[idx << 1].r - L + 1;
        if(node[idx << 1 | 1].L + node[idx << 1 | 1].Lmx - 1 <= r) rd = node[idx << 1 | 1].Lmx;
        else rd = r - node[idx << 1 | 1].L + 1;
        ans += 1LL * ld * rd;
    }
    return ans;
}
void solve() { 
    int n,q;n = read(),q = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    build(1,n,1);
    while(q--) {
        int id;id = read();
        if(id == 1) {
            int x,y;x = read(),y = read();
            update(x,y,1);
        }   
        else {
            int L,r;L = read(),r = read();
            printf("%lld\n",query(L,r,1));
        }
    }

} 
int main() {    
    solve();
    //system("pause");
    return 0;
}
View Code

F：首先可以发现，对于每个X，只有0，5，10三种情况。且0比较特殊不用考虑（周围没有'.')

对于5，显然只有1,4可以构造，10也只有1,1,4,4可以构造。

那么可知对于周围有奇数个的'.'一定不存在解。

考虑对于5的情况。那么X周围的两个一定相反，那么连边后就是二分图的染色。

现在考虑10的情况，猜测肯定也存在解。

且我们相邻点继续连边，染色即可。

如果可以染色即为解，不可以那么说明不存在解。

证明不会。

《Codeforces Round #742 (Div. 2)》
// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tu;
const int N = 2e5 + 5;
const int M = 2e4 + 5;
const double eps = 1e-10;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read() {
    int f = 1;int x = 0;char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
inline long long ADD(long long x,long long y) {return (x + y) % Mod;}
inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;}
inline long long MUL(long long x,long long y) {return x * y % Mod;}

int n,m,deg[505][505],mp[505][505],tot = 0,col[505][505];
pii to[N];
vector<pii> vec;
vector<int> G[N];
string a[505];
bool vis[N],f = 0;
bool check(int x,int y) {
    if(x >= 0 && x < n && y >= 0 && y < m && a[x][y] == '.') return true;
    else return false;
}
void dfs(int u,int c) {
    col[to[u].first][to[u].second] = c;
    vis[u] = 1;
    //printf("u is %d c is %d x is %d y is %d\n",u,c,to[u].first,to[u].second);
    for(auto v : G[u]) {
        if(vis[v]) {
            if(col[to[v].first][to[v].second] == c) f = 1;
        }
        else dfs(v,c ^ 1);
    }
}
int get_tot(int x,int y) {
    if(mp[x][y] == 0) {
        mp[x][y] = ++tot;
        to[tot].first = x;
        to[tot].second = y;
    }
    return mp[x][y];
}
void solve() { 
    n = read(),m = read();
    for(int i = 0;i < n;++i) cin >> a[i];
    for(int i = 0;i < n;++i) {
        for(int j = 0;j < m;++j) {
            if(a[i][j] == 'X') {
                vec.clear();
                if(check(i,j + 1)) deg[i][j]++,vec.push_back(pii{i,j + 1});
                if(check(i,j - 1)) deg[i][j]++,vec.push_back(pii{i,j - 1});
                if(check(i - 1,j)) deg[i][j]++,vec.push_back(pii{i - 1,j});
                if(check(i + 1,j)) deg[i][j]++,vec.push_back(pii{i + 1,j});
                if(deg[i][j] == 0) continue;
                if(deg[i][j] == 1 || deg[i][j] == 3) f = 1;
                else if(deg[i][j] == 2) {
                    int x = get_tot(vec[0].first,vec[0].second);
                    int y = get_tot(vec[1].first,vec[1].second);
                    G[x].push_back(y);
                    G[y].push_back(x);
                }
                else {
                    int x = get_tot(vec[0].first,vec[0].second);
                    int y = get_tot(vec[1].first,vec[1].second);
                    int a = get_tot(vec[2].first,vec[2].second);
                    int b = get_tot(vec[3].first,vec[3].second);
                    G[x].push_back(a);G[a].push_back(x);
                    G[x].push_back(b);G[b].push_back(x);
                    G[y].push_back(a);G[a].push_back(y);
                    G[y].push_back(b);G[b].push_back(y);
                }
            }
        }
    }
    for(int i = 1;i <= tot;++i) {
        if(!vis[i]) {
            dfs(i,0);
        }
    }
    if(f) printf("NO\n");
    else {
        printf("YES\n");
        for(int i = 0;i < n;++i) {
            for(int j = 0;j < m;++j) {
                if(a[i][j] == 'X') {
                    if(deg[i][j] == 2) {
                        col[i][j] = 5;
                    }
                    else if(deg[i][j] == 4) {
                        col[i][j] = 10;
                    } 
                    else col[i][j] = 0;
                }
                else if(col[i][j] == 0) col[i][j] = 1;
                else {
                    col[i][j] = 4;
                }
            }
        }
        for(int i = 0;i < n;++i)
            for(int j = 0;j < m;++j) printf("%d%c",col[i][j],j == m - 1 ? '\n' : ' ');

    }

} 
int main() {    
    solve();
   // system("pause");
    return 0;
}
View Code

 

上一篇：判断两台设备是否属于同一子网的简易程序(C++实现)


下一篇：Android屏幕元素层次结构