1002 C++ to Python

Meaning:

Use (...) in python to match std:: make in C++_ tuple(...)

Solution:

Sign in, just ignore letters, underscores, colons and output.

code:

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#define int long long
using namespace std;

string s;

void solve(){
    cin >> s;
    int len = s.length();
    for(int i = 0; i < len; i++){
        if(s[i] == '(' || s[i] == ')' || s[i] == ',' || s[i] == '-') 
            cout << s[i];
        if(s[i] >= '0' && s[i] <= '9') 
            cout << s[i];
    }
    cout << '\n';
}

signed main(){
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
}

1007 Snatch Groceries

Meaning:

There are n people who want to obtain supplies. Each person is given a time interval. If the time interval of the two people does not intersect, the priority relationship between the two people can be determined. The computer will distribute materials in chronological order. In case of failure to determine the priority, the distribution will be stopped. Ask how many people can get supplies.

(the original question is so long that he kindly wrote "TL;DR", which means Too Long; Didn't Read, but I didn't understand it.)

Solution:

The left end point of the time interval is the first keyword, and the right end point is the second keyword. Then scan from the first to the back and verify.

code:

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;

const int N = 1e5 + 10;

int n;

struct time{
    int l, r;
    bool operator < (const time x) const{
        return l < x.l || (l == x.l && r < x.r);
    }
}a[N];

void solve(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i].l >> a[i].r;
    }
    sort(a + 1, a + 1 + n);
    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(i == n){
            ans ++;
            break;
        }
        if(a[i + 1].l > a[i].r) ans ++;
        else break;
    }
    cout << ans << '\n';
}

signed main(){
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
}

1012 Luxury cruise ship

Meaning:

Given n, 7, 31365 can be saved every day. It takes at least a few days to just save to N. if not, output -1.

Solution:

79205 is a cycle, which can be pretreated with backpack or bfs and then calculated.

(code is bfs preprocessing)

code;

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#define int long long
using namespace std;

const int N = 79205 + 10;

int n, ans[N], vis[N];

struct node{
    int num, cnt;
};

void bfs(){
    memset(ans, -1, sizeof(ans));
    memset(vis, 0, sizeof(vis));
    queue<node> q;
    q.push({0, 0});
    while(!q.empty()){
        node x = q.front(); q.pop();
        if(vis[x.num]) continue;
        vis[x.num] = 1;
        ans[x.num] = x.cnt;
        if(x.num + 7 <= 79205) q.push({x.num + 7, x.cnt + 1});
        if(x.num + 31 <= 79205) q.push({x.num + 31, x.cnt + 1});
        if(x.num + 365 <= 79205) q.push({x.num + 365, x.cnt + 1});
    }
}

void solve(){
    cin >> n;
    if(ans[n % 79205] != -1)
        cout << n / 79205 * (7 * 31) + ans[n % 79205] << '\n';
    else cout << -1 << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    bfs();
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
}

1009 ShuanQ

Meaning:

Another unknown module m, P, Q is about the inverse element relationship of M. The given encryption and decryption formulas are:

encrypted_data = raw_data × P mod M

raw_data = encrypted_data × Q mod M

Given P, Q and encrypted_data, ask if you can confirm raw_data, if there is no solution, output "shuanQ".

Where, m>p, Q are prime numbers.

(I really shaunQ)

Solution:

From the inverse relation, we can know:

P × Q − 1 = k × M , k ≥ 1

So we can enumerate k and calculate raw with the obtained legal M_ Data, and verify whether there is a unique solution.

code:

#include<iostream>
#include<algorithm>
#define int long long
using namespace std;

int x, p, q;

void solve(){
    cin >> p >> q >> x;
    int km = p * q - 1, ans = -1, m;
    for(int i = 2; i * i <= km; i++){
        if(km % i) continue;
        while(km % i == 0) km /= i;
        m = i; 
    }
    if(km > 1) m = km;
    if(q < m && p < m) ans = x * q % m;
    if(~ans) cout << ans << '\n';
    else cout << "shuanQ\n";
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1; 
    cin >> t;
    while(t--){
        solve();
    }
}

1001 Static Query on Tree

Meaning:

Given A tree with n nodes, ask q times, each time for A set of three nodes A,B,C, and ask how many nodes in the tree can reach at least one point in A and at least one point in B, and at least one point in C.

Solution:

Mark each node in A and B to the root node with A and B, mark each node in C and their subtrees with C, and count the number of nodes marked with A, B, and C at the same time.

code:

#include<iostream>
#include<vector>
#include<bitset>
using namespace std;
#define int long long
#define lson (p << 1)
#define rson (p << 1 | 1)

const int N = 2e5 + 10;

struct tree{
    int mx[3], mn[3], flag[3];
};

int tot = 0, fa[N], son[N], siz[N], top[N], dep[N];
int dfn[N], rnk[N], a[3][N];
vector<int> edg[N];
tree tr[N << 2];

int n, m[3];

struct Tree{
#define lson (p << 1)
#define rson (p << 1 | 1)

void dfs1(int x){
    siz[x] = 1, son[x] = -1;
    for(int to : edg[x]){
        if(to == fa[x]) continue;
        dep[to] = dep[x] + 1;
        fa[to] = x;
        dfs1(to);
        siz[x] += siz[to];
        if(son[x] == -1 || siz[to] > siz[son[x]]) son[x] = to;
    }
}

void dfs2(int x, int t){
    top[x] = t;
    dfn[x] = ++tot;
    rnk[tot] = x;
    if(son[x] == -1) return;
    dfs2(son[x], t);
    for(int to : edg[x]){
        if(to == fa[x] || to == son[x]) continue;
        dfs2(to, to);
    }
}

void pushup(int p){
    for(int i = 0; i < 3; i++){
        tr[p].mx[i] = tr[lson].mx[i] | tr[rson].mx[i];
        tr[p].mn[i] = tr[lson].mn[i] & tr[rson].mn[i];
    }
}

void pushdown(int p){
    for(int i = 0; i < 3; i++){
        if(tr[p].flag[i] == 0) continue;
        tr[lson].mn[i] = tr[p].flag[i] - 1;
        tr[rson].mn[i] = tr[p].flag[i] - 1;
        tr[lson].mx[i] = tr[p].flag[i] - 1;
        tr[rson].mx[i] = tr[p].flag[i] - 1;
        tr[lson].flag[i] = tr[p].flag[i];
        tr[rson].flag[i] = tr[p].flag[i];
        tr[p].flag[i] = 0;
    }
}

void update(int s, int t, int x, int y, int l = 1, int r = n, int p = 1){
    if(s <= l && r <= t){
        tr[p].mx[x] = y;
        tr[p].mn[x] = y;
        tr[p].flag[x] = y + 1;
        return;
    }
    if(tr[p].flag[0] || tr[p].flag[1] || tr[p].flag[2]) pushdown(p);
    int mid = (l + r) >> 1;
    if(s <= mid) update(s, t, x, y, l, mid, lson);
    if(mid < t) update(s, t, x, y, mid + 1, r, rson);
    pushup(p);
}

int query(int l = 1, int r = n, int p = 1){
    if(tr[p].mn[0] && tr[p].mn[1] && tr[p].mn[2]) return r - l + 1;
    if(!tr[p].mx[0] || !tr[p].mx[1] || !tr[p].mx[2]) return 0;
    if(l == r) return 0;
    if(tr[p].flag[0] || tr[p].flag[1] || tr[p].flag[2]) pushdown(p);
    int mid = (l + r) >> 1;
    int res = 0;
    res += query(l, mid, lson);
    res += query(mid + 1, r, rson);
    return res;
}

void up(int x, int y, int z, int zz){
    while(top[x] != top[y]){
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        update(dfn[top[x]], dfn[x], z, zz);
        x = fa[top[x]];
    }
    if(dfn[x] < dfn[y]) update(dfn[x], dfn[y], z, zz);
    else update(dfn[y], dfn[x], z, zz);
}

}Tree;

void solve(){
    for(int i = 0; i < (N << 2); i ++){
        for(int j = 0; j <= 2; j ++){
            tr[i].mx[j] = tr[i].mn[j] = tr[i].flag[j] = 0;
        }
    }
    int q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        edg[i].clear();
    }
    for(int i = 2; i <= n; i++){
        int x; cin >> x;
        edg[i].push_back(x);
        edg[x].push_back(i);
    }
    tot = 0; dep[1] = 1; Tree.dfs1(1); Tree.dfs2(1, 1);
    while(q--){
        cin >> m[0] >> m[1] >> m[2];
        for(int j = 0; j <= 2; j++){
            for(int i = 1; i <= m[j]; i++){
                cin >> a[j][i];
            }
        }
        for(int j = 0; j <= 1; j ++){
            for(int i = 1; i <= m[j]; i++){
                Tree.up(1, a[j][i], j, 1);
            }
        }
        for(int i = 1; i <= m[2]; i++){
            Tree.update(dfn[a[2][i]], dfn[a[2][i]] + siz[a[2][i]] - 1, 2, 1);
        }
        cout << Tree.query() << '\n';
        for(int j = 0; j <= 1; j ++){
            for(int i = 1; i <= m[j]; i ++){
                Tree.up(1, a[j][i], j, 0);
            }
        }
        for(int i = 1; i <= m[2]; i++){
            Tree.update(dfn[a[2][i]], dfn[a[2][i]] + siz[a[2][i]] - 1, 2, 0);
        }
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
}

1004 Keychains

Meaning:

Given the center points and normal vectors of two rings in the three-dimensional coordinate system, ask whether the two rings are connected.

Solution:

You can find the intersection of the plane where A ring and B ring are located. One intersection is outside b ring and the other is inside b ring. This is equivalent to finding the intersection of A sphere and B plane, and then equivalent to the intersection of A sphere and (the intersection line of A plane and B plane).

Using vectors will avoid many problems.

Code: (teammate's)

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
#define double long double
const double eps = 1e-9;
 
struct dot
{
    double x, y, z;
    dot(double xx = 0, double yy = 0, double zz = 0) : x(xx), y(yy), z(zz){}
};
inline void print(dot &a){cout << a.x << " " << a.y << " " << a.z << endl;}
 
inline dot operator + (const dot &a, const dot &b){return dot(a.x + b.x, a.y + b.y, a.z + b.z);}
inline dot operator - (const dot &a, const dot &b){return dot(a.x - b.x, a.y - b.y, a.z - b.z);}
inline double len(const dot &a){return sqrt(a.x * a.x + a.y * a.y + a.z * a.z);}
inline double operator * (const dot &a, const dot &b){return a.x * b.x + a.y * b.y + a.z * b.z;}
inline dot operator * (const double &k, const dot &a){return dot(k * a.x, k * a.y, k * a.z);}
inline dot operator / (const dot &a, const double &k){return dot(a.x / k, a.y / k, a.z / k);}
inline dot operator ^ (const dot &a, const dot &b){return dot(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x);}
inline dot unit(const dot &a){return a / len(a);}//Unit vector
 
struct line
{
    dot d, a, b;
    line(dot dd, dot aa) : d(unit(dd)), a(aa), b(aa + unit(dd)){}
};
 
struct cir
{
    dot o;
    double r;
    cir(double x = 0, double y = 0, double z = 0, double rr = 0) : o(dot(x, y, z)), r(rr){}
}; 
 
inline dot vert(const line &l, const dot &o)//Drop foot
{
    return l.a + ((o - l.a) * l.d) * l.d;
}
 
inline double calc(double x, double y){return sqrt(x * x - y * y);}
inline vector<dot> cross_line_cir(const cir &c, const line &l)
{
    vector<dot> res;
    dot x = vert(l, c.o);
    double dd = len(x - c.o);
    if(c.r < dd - eps)return res;
    if(abs(c.r - dd) < eps)
    {
        res.push_back(x);
        return res;
    }
    double dis = calc(c.r, dd);
    res.push_back(x + dis * l.d);
    res.push_back(x - dis * l.d);
    return res;
}
 
inline dot intion(dot p1, dot d1, dot p2, dot d2)
{
    dot e = d1 ^ d2;
    dot u = d1 ^ e;
    return p1 + ((p2 - p1) * d2) / (u * d2) * u;
}
 
inline bool incir(const cir &c, const dot &o){return len(o - c.o) < c.r - eps;}
inline bool outcir(const cir &c, const dot &o){return len(o - c.o) > c.r + eps;}
 
cir c[3];
dot f[3];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _;
    cin>>_;
    while(_--)
    {
        for(int i = 1; i <= 2; ++i)
        cin >> c[i].o.x >> c[i].o.y >> c[i].o.z >> f[i].x >> f[i].y >> f[i].z >> c[i].r;
        line l(f[1] ^ f[2], intion(c[1].o, f[1], c[2].o, f[2]));
        // print(l.a);
        vector<dot> ans = cross_line_cir(c[1], l);
        if(ans.size() < 2)
        {
            cout << "No\n";
            continue;
        }
        // print(ans[0]);print(ans[1]);
        //if((incir(c[2],ans[0])&&outcir(c[2],ans[1]))||(outcir(c[2],ans[0])&&incir(c[2],ans[1])))
        if(incir(c[2], ans[0]) ^ incir(c[2], ans[1]))
        cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

1003 Copy

Meaning:

Given a sequence of numbers, q operations, operation 1 copies the l-r interval and adds it to the end of the l-r interval, operation 2 queries the number of x, and the answer is the exclusive or sum of the queried numbers.

Solution:

One copy is equivalent to subtracting (r-l+1) all the following queries >r, and because l, R, x are less than n, and the output of the answer is XOR and (XOR twice equals 0), bitset can be used to maintain the answer. You can also divide the interval intoBlock. Only three blocks will be added for each operation. When implementing, save the index of the block and the prefix and sum of the block size.

You can also do it in blocks and find two teammates to learn the code.

bitset Code:

#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<bitset>
using namespace std;
#define debug(x) cout<<#x<<" "<<(x)<<endl
#define debug2(x,y) cout<<#x<<endl;for(int i=1;i<=y;++i)cout<<x[i]<<" ";cout<<endl
#define mem(x,y) memset(x,y,sizeof(x));
#define int long long
#define double long double
const int inf=0x3f3f3f3f3f3f3f3f;
const double eps=1e-9;
const double PI=acos(-1.0);
const int maxn=1e5+10;
 
struct Que
{
    int flg,l,r;
};
 
int n;
int a[maxn];
bitset<maxn> res;
Que que[maxn];
 
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // cout<<fixed<<setprecision(6);
    int _;
    cin>>_;
    while(_--)
    {
        int q;
        cin>>n>>q;
        for(int i=1;i<=n;++i)
        res[i]=0;
        for(int i=1;i<=n;++i)
        cin>>a[i];
        
        for(int i=1;i<=q;++i)
        {
            cin>>que[i].flg>>que[i].l;
            if(que[i].flg==1)cin>>que[i].r;
        }
        for(int i=q;i>=1;--i)
        {
            if(que[i].flg==1)
            {
                bitset<maxn> l=(~bitset<maxn>(0)>>(maxn-que[i].r-1))&res;
                bitset<maxn> r=(~bitset<maxn>(0)<<(que[i].r+1))&res;
                res=l^(r>>(que[i].r-que[i].l+1));
            }
            if(que[i].flg==2)
            res[que[i].l]=res[que[i].l]^1;
        }
        int ans=0;
        for(int i=1;i<=n;++i)
        if(res[i])ans^=a[i];
        cout<<ans<<'\n';
    }
    return 0;
}

Block code:

#include<iostream>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
#define debug(x) cout<<#x<<" "<<(x)<<endl
#define debug2(x,y) cout<<#x<<endl;for(int i=1;i<=y;++i)cout<<x[i]<<" ";cout<<endl
#define mem(x,y) memset(x,y,sizeof(x));
#define int long long
#define double long double
const int inf=0x3f3f3f3f3f3f3f3f;
const double eps=1e-9;
const double PI=acos(-1.0);
const int maxn=2e6+10;
const int s=350;
 
int n;
int a[maxn];
vector<int> blk[maxn];
int sum[maxn],pos[maxn];
 
void solve()
{
    int q;
    cin>>n>>q;
    for(int i=1;i<=n;++i)
    cin>>a[i];
    for(int i=1;i<=n;++i)
    blk[i].clear();
    for(int i=1;i<=n;++i)
    {
        blk[(i-1)/s+1].push_back(a[i]);
        sum[(i-1)/s+1]=i;
    }
    int tot=(n-1)/s+1;
    int num=tot;
    for(int i=1;i<=tot;++i)
    pos[i]=i;
    int flg,l,r,x;
    int ans=0;
    while(q--)
    {
        cin>>flg;
        if(flg==1)
        {
            cin>>l>>r;
            int ll=lower_bound(sum+1,sum+num+1,l)-sum;
            int rr=lower_bound(sum+1,sum+num+1,r)-sum;
            l-=sum[ll-1];
            r-=sum[rr-1];
            if(ll==rr)
            {
                ++tot;
                blk[tot].clear();
                for(int i=0;i<r;++i)
                blk[tot].push_back(blk[pos[ll]][i]);
                ++tot;
                blk[tot].clear();
                for(int i=l-1;i<r;++i)
                blk[tot].push_back(blk[pos[ll]][i]);
                ++tot;
                blk[tot].clear();
                for(int i=r;i<(int)blk[pos[ll]].size();++i)
                blk[tot].push_back(blk[pos[ll]][i]);
                vector<int> t;
                t.push_back(tot-2);
                t.push_back(tot-1);
                t.push_back(tot);
                for(int i=ll+1;i<=num;++i)
                t.push_back(pos[i]);
                for(int i=0;i<(int)t.size();++i)
                {
                    pos[ll+i]=t[i];
                    sum[ll+i]=sum[ll+i-1]+blk[t[i]].size();
                    if(sum[ll+i]>=n)
                    {
                        num=ll+i;
                        break;
                    }
                }
            }
            else
            {
                ++tot;
                blk[tot].clear();
                for(int i=l-1;i<(int)blk[pos[ll]].size();++i)
                blk[tot].push_back(blk[pos[ll]][i]);
                ++tot;
                blk[tot].clear();
                for(int i=0;i<r;++i)
                blk[tot].push_back(blk[pos[rr]][i]);
                ++tot;
                blk[tot].clear();
                for(int i=r;i<(int)blk[pos[rr]].size();++i)
                blk[tot].push_back(blk[pos[rr]][i]);
                vector<int> t;
                t.push_back(tot-1);
                t.push_back(tot-2);
                for(int i=ll+1;i<rr;++i)
                t.push_back(pos[i]);
                t.push_back(tot-1);
                t.push_back(tot);
                for(int i=rr+1;i<=num;++i)
                t.push_back(pos[i]);
                for(int i=0;i<(int)t.size();++i)
                {
                    pos[rr+i]=t[i];
                    sum[rr+i]=sum[rr+i-1]+blk[t[i]].size();
                    if(sum[rr+i]>=n)
                    {
                        num=rr+i;
                        break;
                    }
                }
            }
        }
        else
        {
            cin>>x;
            int t=lower_bound(sum+1,sum+num+1,x)-sum;
            ans^=blk[pos[t]][x-sum[t-1]-1];
        }
    }
    cout<<ans<<'\n';
}
 
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // cout<<fixed<<setprecision(6);
    int _;
    cin>>_;
    while(_--)
    {
        solve();
    }
    return 0;
}

1011 DOS Card

Meaning:

Given n cards, m queries, each query given an interval, it is required to draw four cards in the changed interval, and combine them in pairs. The value of each pair isWhere I < J, the total value is the sum of two pairs of values and the maximum value of the total value.

Solution:

Looking at the code specifically, I learned from my classmates' code, and I believe that seeing the variable name must be enlightening.

code:

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
using namespace std;
#define int long long
#define double long double
#define INF 0x3f3f3f3f3f3f3f3f
#define eps 1e-9

const int N = 2e5 + 10;

struct node{
    int d, x, xx, dd, dx, xd, dxd, xdx, ddx, dxx, dxdx, ddxx;
    void init(){
        d = x = xx = dd = dx = xd = dxd = xdx = ddx = dxx = dxdx = ddxx = -INF;
    }
    node operator + (const node &r) const{
        node res;
        res.init();
        res.d = max(d, r.d);
        res.x = max(x, r.x);
        res.xx = max({xx, r.xx, x + r.x});
        res.dd = max({dd, r.dd, d + r.d});
        res.xd = max({xd, r.xd, x + r.d});
        res.dx = max({dx, r.dx, d + r.x});
        res.ddx = max({ddx, r.ddx, dd + r.x, d + r.dx});
        res.dxd = max({dxd, r.dxd, dx + r.d, d + r.xd});
        res.dxx = max({dxx, r.dxx, d + r.xx, dx + r.x});
        res.xdx = max({xdx, r.xdx, x + r.dx, xd + r.x});
        res.ddxx = max({ddxx, r.ddxx, d + r.dxx, dd + r.xx, ddx + r.x});
        res.dxdx = max({dxdx, r.dxdx, d + r.xdx, dx + r.dx, dxd + r.x});
        return res;
    }
};
int n, a[N];
node tr[N << 2];

struct tree{
#define ls (p << 1)
#define rs (p << 1 | 1)

void build(int l = 1, int r = n, int p = 1){
    tr[p].init();
    if(l == r){
        tr[p].x = -a[l] * a[l];
        tr[p].d = a[l] * a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(l, mid, ls);
    build(mid + 1, r, rs);
    tr[p] = tr[ls] + tr[rs];
}

node query(int s, int t, int l = 1, int r = n, int p = 1){
    if(s <= l && r <= t) return tr[p];
    int mid = (l + r) >> 1;
    if(t <= mid) return query(s, t, l, mid, ls);
    else if(mid < s) return query(s, t, mid + 1, r, rs);
    else return query(s, t, l, mid, ls) + query(s, t, mid + 1, r, rs);
}

}tree;

void solve(){
    int q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    tree.build();
    int l, r;
    while(q--){
        cin >> l >> r;
        node ans = tree.query(l, r);
        cout << max(ans.ddxx, ans.dxdx) << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    cin >> t;
    while(t--){
        solve();
    }
}