2022“杭电杯”中国大学生算法设计超级联赛（2）题解报告

1002 C++ to Python 题意：

在python中使用（...）来匹配C++中的std::make_tuple(...)

题解：

签到，只要无视字母、下划线、冒号后输出即可。

代码：

#include
#include
#include
#include
#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 题意：

有n个人想获取物资，每个人给定一个时间区间，如果两人的时间区间没有交集，那就可以确定两人的先后关系。电脑按照时间顺序发放物资，遇到无法确定先后关系的情况，停止发放。问有几个人能拿到物资。

（原题题面巨长，他好心写了“TL;DR”， 意为 Too Long; Didn't Read， 但是我没看懂）

题解：

按时间区间左端点为第一关键字，右端点第二关键字排序，然后从第一个往后一边扫一边验证即可。

代码：

#include
#include
#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 题意：

给定N，每天可以存7， 31， 365， 最少需要几天可以刚好存到N， 不行则输出-1。

题解：

79205为一周期，可以使用背包或bfs预处理，再进行计算。

（代码为bfs预处理）

代码;

#include
#include
#include
#include
#include
#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 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 题意：

又一个未知的模数M，P、Q是关于M的逆元关系。给定加密与解密公式分别为：

encrypted_data = raw_data × P mod M

raw_data = encrypted_data × Q mod M

给定P、Q和encrypted_data，问能否确定raw_data，无解则输出“shuanQ”。

其中，M>P、Q且为素数。

（我真的shaunQ）

题解：

由逆元关系我们可以知道：

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

于是我们可以枚举k，用得到的合法的M来计算raw_data，并验证是否有唯一解。

代码：

#include
#include
#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 << "shuanQn";
}

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 题意：

给定一棵n个节点的树，q次询问，每次询问给定三个节点的集合A,B,C，问树中有多少个节点是可以从A中至少一点和B中至少一点到达，并且到达C中至少一点。

题解：

将A和B中每个节点到根节点打上A和B的标记，将C中的每个节点及他们的子树打上C标记，统计同时有A,B,C标记的节点数即可。

代码:

#include
#include
#include
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 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 题意:

给定三维坐标系中两个圆环的圆心和法向量，问两个圆环是否相扣。

题解:

可以求A环与B环所在的平面的交点，交点一个在B环外面，一个在B环里面就YES，这样等价于求A球于B平面交点，再等价于A球与（A平面与B平面的交线）的交点。

用向量做会避免很多问题。

代码：（队友的）

#include
#include
#include
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);}//单位向量
 
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)//垂足
{
    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 cross_line_cir(const cir &c, const line &l)
{
    vector 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 ans = cross_line_cir(c[1], l);
        if(ans.size() < 2)
        {
            cout << "Non";
            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 << "Yesn";
        else cout << "Non";
    }
    return 0;
}

1003 Copy 题意：

给定一个数列，q次操作，1操作复制l-r区间加在l-r区间后面，2操作查询第x个是多少，答案为查询的数字的异或和。

题解：

一次复制相当于把下面所有>r的查询减去（r-l+1），又因为l，r，x都是小于n，而答案输出的又是异或和（异或两次等于0）所以可以用bitset是维护答案。也可以把区间分为块，每次操作只会增加三块，实现时存一下块的索引和块大小的前缀和。

也可以分块做，找了两份队友的代码学习。

bitset代码：

#include
#include
#include
#include
#include
using namespace std;
#define debug(x) cout<<#x<<" "<<(x)< res;
Que que[maxn];
 
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // cout<>_;
    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 l=(~bitset(0)>>(maxn-que[i].r-1))&res;
                bitset r=(~bitset(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<

 分块代码：

#include
#include
#include
#include
#include
#include
using namespace std;
#define debug(x) cout<<#x<<" "<<(x)< 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 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 t;
                t.push_back(tot-1);
                t.push_back(tot-2);
                for(int i=ll+1;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<>_;
    while(_--)
    {
        solve();
    }
    return 0;
}

1011 DOS Card 题意：

给定n张牌m次查询，每次查询给定一个区间，要求在改区间内抽四张牌，两两组合，每一对的值为，其中i < j，总值为两对值的和，问总值的最大值。

题解：

具体看代码，借鉴了同学的代码，相信看到变量名一定茅塞顿开。

代码：

#include
#include
#include
#include
#include
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();
    }
}