2022SDNU-ACM結(jié)訓(xùn)賽題解-創(chuàng)新互聯(lián)

出題人: LYJ

本來(lái)沒想出hello world的題，但是突然接到通知大二不打了，這套題只給大一打，我就連夜加了一道

如果沒有這個(gè)題，大家很可能五個(gè)小時(shí)都在牢底坐穿

還是要祝一下蛇姐生日快樂耶！

輸出”蛇姐生日快樂!!!”即可

#includeusing namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pairpii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];

void work(){cout<< "蛇姐生日快樂!!!";
}

int main(){io;
    work();
    return 0;
}

出題人: NXY

關(guān)于xygg出了個(gè)權(quán)值線段樹卻被兩個(gè)人用別的思路隨便卡過去這件事

第一種做法：離散化 + 權(quán)值線段樹
我們發(fā)現(xiàn)每個(gè)數(shù)本身沒有什么用，我們需要的僅僅是他們之間的大小關(guān)系，而 N N N 又不是很大，所以考慮離散化。
然后把離散化之后的序列用權(quán)值線段樹維護(hù)起來(lái)。

第二種做法：平衡樹
動(dòng)態(tài)查詢第 k k k 大數(shù)，容易想到平衡樹直接維護(hù)

第三種做法：對(duì)頂堆
szz \texttt{szz} szz 的考場(chǎng)做法。

第四種做法: 主席樹
gts \texttt{gts} gts 的考場(chǎng)做法

大家如果要補(bǔ)題的話建議學(xué)習(xí)第一種做法和第三種做法，第一種做法很典型很常見，是一種必不可少的技能點(diǎn)。第三種做法思維上很巧妙很有意思，并且代碼簡(jiǎn)短容易理解，也同樣建議大家學(xué)習(xí)

#includeusing namespace std;
const int N = 1e5 + 10;

int n,w;
int a[N],b[N],c[N];

bool cmp(int x , int y)
{return x >y;}

struct NO
{int l;
    int r;
    int w;
};

struct SigmentT
{NO t[N * 4];
    void Build(int p , int l , int r)
    {t[p].l = l; t[p].r = r;
        if(l == r) return;
        int mid = (l + r) >>1;
        Build(p<< 1 , l , mid);
        Build(p<< 1 | 1 , mid + 1 , r);
    }

    void Updata(int p , int w)
    {if(t[p].l == t[p].r) {t[p].w++; return;
        }
        int mid = (t[p].l + t[p].r) >>1;
        if(w<= mid) Updata(p<< 1 , w);
        else Updata(p<< 1 | 1 , w);
        t[p].w = t[p<< 1].w + t[p<< 1 | 1].w;
    }

    int Query(int p , int k)
    {if(t[p].l == t[p].r) return t[p].l;
        if(t[p<< 1].w< k) return Query(p<< 1 | 1, k - t[p<< 1].w);
        else return Query(p<< 1 , k);
    }
}tr;

int main()
{//freopen("aa.in","r",stdin);
    scanf("%d%d",&n,&w); 
    for(int i = 1; i<= n; i++)
        scanf("%d",&a[i]) , b[i] = a[i];

    std::sort(b + 1 , b + 1 + n);
    int LEN = std::unique(b + 1 , b + 1 + n) - b - 1;
    for(int i = 1, tmp; i<= n; i++)
        tmp = a[i] , a[i] = std::lower_bound(b + 1 , b + 1 + LEN , a[i]) - b , c[a[i]] = tmp;
    
    tr.Build(1 , 0 , LEN);
    for(int i = 1; i<= n; i++)
    {int m = max(1 , i * w / 100);
        tr.Updata(1 , a[i]);
        printf("%d ",c[tr.Query(1 , i - m + 1)]);
    }
    
}

#includeconst int N = 3e5 + 10;

int n,w;
int a[N];

struct No {int p,siz,val,sel,son[2];
};

struct SBT{int rt,idx;
    No t[N];

    void Pushup(int u) {t[u].siz = t[t[u].son[0]].siz + t[t[u].son[1]].siz + t[u].sel;
    }

    void rotate(int u) {int y = t[u].p , z = t[y].p;
        int k = t[y].son[1] == u;
        t[z].son[t[z].son[1] == y] = u , t[u].p = z;
        t[y].son[k] = t[u].son[k ^ 1] , t[t[u].son[k ^ 1]].p = y;
        t[u].son[k ^ 1] = y , t[y].p = u;
        Pushup(y) , Pushup(u);
    }

    void Splay(int u , int p) {while(t[u].p != p) {int y = t[u].p , z = t[y].p;
            if(z != p)
                if((t[z].son[1] == y) ^ (t[y].son[1] == u))
                    rotate(u);
                else rotate(y);
            rotate(u);
        }
        if(!p) rt = u;
    }

    void insert(int val) {int u = rt , p = 0;
        while(u) {if(val == t[u].val) break;
            p = u , u = t[u].son[val >t[u].val];
        }
        if(!u) u = ++idx;
        t[u].sel++;t[u].p = p;t[u].val = val;
        if(p) t[p].son[val >t[p].val] = u;
        Splay(u , 0);
    }

    int getk(int k) {int u = rt;
        while(1) {if(k<= t[t[u].son[0]].siz) u = t[u].son[0];
            else if(k<= t[t[u].son[0]].siz + t[u].sel) {Splay(u , 0); return t[u].val;
            }
            else k -= t[t[u].son[0]].siz + t[u].sel , u = t[u].son[1];
        }
    }
}tr;

const int inf = 1e9;

int main() {//freopen("aa.in","r",stdin);
    scanf("%d%d",&n,&w); tr.insert(-1) , tr.insert(inf);
    for(int i = 1 , x; i<= n; i++) {scanf("%d",&x); tr.insert(x);
        int end = std::max(1 , i * w / 100);
        printf("%d ",tr.getk(i - end + 1 + 1));
    }
}

出題人: DJK

看hard版之前先看看easy版的

跟簡(jiǎn)單版相比，不同點(diǎn)在于字符串長(zhǎng)度，和操作總次數(shù)發(fā)生了變化。

給出其中一種構(gòu)造方式。

由于是對(duì)前綴進(jìn)行操作，容易想到從后向前匹配兩個(gè)01串，當(dāng) s 串 與 t 串 s串與t串 s串與t串在位置 i i i不同時(shí)，執(zhí)行操作 i i i,但當(dāng)執(zhí)行完操作 i i i后， s 串 和 t 串 s串和t串 s串和t串在位置 i i i依舊可能不匹配，所以我們需要預(yù)處理 s s s串，讓它全變成 0 0 0或 1 1 1，這樣的話就可以保證執(zhí)行操作 i i i后，一定匹配。

容易發(fā)現(xiàn)，至多操作 2 ? n 2*n 2?n次（預(yù)處理至多 n n n次，從后向前匹配過程至多 n n n次）。

#includeusing namespace std;
typedef long long ll;
//#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define pii pairconst int maxn = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const double eps = 1e-4;
int n, sum;
string s1, s2;
char ch;
int ans[maxn];

int main()
{io;
    //freopen("20.in", "r", stdin);
    //freopen("20.out", "w", stdout);
    cin >>s1 >>s2;
    n = s1.size();
    s1 = '$' + s1;
    s2 = '$' + s2;
    sum = 0;
    for(int i = 2; i<= n; ++i)
    {if(s1[i] != s1[i - 1])
            ans[++sum] = i - 1;
    }
    ch = s1[n] - '0';
    for(int i = n; i >0; --i)
    {if(ch != (s2[i] - '0'))
        {ans[++sum] = i;
            ch = 1 - ch;
        }
    }
    cout<< sum;
    for(int i = 1; i<= sum; ++i) cout<< ' '<< ans[i];
    cout<< '\n';
    return 0;
}

出題人：NXY

a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊a+b啊

這個(gè)題最開始的時(shí)候是NXY想考ull自然溢出等于對(duì)2⁶⁴取模，所以題目名稱本來(lái)叫做**“自然溢出啥事沒有!”**，但是有狗提議改把a(bǔ)和b的數(shù)字的長(zhǎng)度改到1e5，使得NXY卡了一下py（

需要用到的知識(shí)點(diǎn)有兩個(gè)：

• unsigned long long自然溢出等價(jià)于對(duì) 2 64 2^{64} 264 取模，也就是說(shuō)自然溢出啥事沒有!
• ( a × b + c ) ? % ? p = ( ( a × b ) ? % ? p + c ? % ? p ) ? % ? p (a\times b + c)\ \%\ p = ((a\times b)\ \%\ p+c\ \%\ p)\ \%\ p (a×b+c)?%?p=((a×b)?%?p+c?%?p)?%?p

因此我們只需要把輸入的數(shù) a a a 分解為 a = x ? 10 + c a = x * 10 + c a=x?10+c即可

NXY 特意卡了 python

#includeusing namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef unsigned long long ull;
typedef pairpii;

#define MAX 300000 + 50
string s;
ull a, b;

void work(){cin >>s;
    a = b = 0;
    for(auto x : s){a = a * 10 + (ull)(x - '0');
    }
    cin >>s;
    for(auto x : s){b = b * 10 + (ull)(x - '0');
    }
    cout<< (ull)(a+b)<io;
    work();
    return 0;
}

出題人: BHQ

防AK題

一個(gè)手鏈上有 n n n 個(gè)珠子，有 n n n 種顏色，給每個(gè)珠子都染上顏色。有多少種不同的染色方法。由于方案數(shù)很多，請(qǐng)對(duì) 998244353 998244353 998244353 取模。

Pólya 計(jì)數(shù)的裸題，很難，想了解可以自己了解。

#include#include

出題人: WYY

M條出售記錄，每條出售記錄由物品名稱、收貨地、出售數(shù)目組成。

請(qǐng)按如下規(guī)則進(jìn)行統(tǒng)計(jì)并輸出：物品按收貨地分類，并合并出售數(shù)目,收貨地按字典序排列，同一收貨地的物品按字典序排列。

很簡(jiǎn)單的模擬題，沒什么意思

#pragma GCC optimize(3)
#includeusing namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pairpii;

#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
string s, t;

struct ran{string s;
    mapmp;
}tr[105];

void work(){cin >>n;
    for(int i = 1; i<= 100;++i)tr[i].mp.clear();
    mapmp;
    int tot = 0;
    for(int i = 1; i<= n; ++i){cin >>s >>t >>x;
        if(!mp.count(t))mp[t] = ++tot;
        tr[mp[t]].s = t;
        tr[mp[t]].mp[s]+=x;
    }
    for(auto [x,y] : mp){cout<< tr[y].s<< endl;
        cout<< "--------------------\n";
        for(auto [u, v] : tr[y].mp){cout<< "    ";
            cout<< u<< "("<io;
    int tt;cin>>tt;
    for(int _t = 1; _t<= tt; ++_t){work();
        if(_t != tt)cout<< endl;
    }
    return 0;
}

出題人: DJK

脫離題干背景，單純考慮區(qū)間操作，發(fā)現(xiàn)題意如下：

給你一個(gè)長(zhǎng)度為 n ( 1 ≤ n ≤ 5 ? 1 0 5 ) n(1≤n≤5*10^5) n(1≤n≤5?105)的數(shù)組。你需要將其分成幾段連續(xù)的子區(qū)間，每一段區(qū)間的權(quán)值如下：

• 若區(qū)間和大于0，則為區(qū)間長(zhǎng)度
• 如區(qū)間和等于0，則為0
• 如區(qū)間和小于0，則為區(qū)間長(zhǎng)度的相反數(shù)

用一個(gè)式子表示即： v a l [ l , r ] = s i g n ( s u m [ l , r ] ) ? ( r ? l + 1 ) val[l,r] = sign(sum[l,r]) * (r - l + 1) val[l,r]=sign(sum[l,r])?(r?l+1) ( v a l [ l , r ] 表 示 區(qū) 間 [ l , r ] 的 權(quán) 值 , s i g n 函 數(shù) 同 原 題 中 的 f 函 數(shù) ， s u m [ l , r ] 亦 相 同 ) (val[l,r]表示區(qū)間[l,r]的權(quán)值,sign函數(shù)同原題中的f函數(shù)，sum[l,r]亦相同) (val[l,r]表示區(qū)間[l,r]的權(quán)值,sign函數(shù)同原題中的f函數(shù)，sum[l,r]亦相同)

問你分出來(lái)的子區(qū)間的權(quán)值和大為多少，并且是否大于等于 H H H。

數(shù)據(jù)結(jié)構(gòu)優(yōu)化DP

我們首先考慮暴力解法。

定義 d p [ i ] dp[i] dp[i]為 [ 1 , i ] [1,i] [1,i]中的大權(quán)值和，容易發(fā)現(xiàn)可以 O ( n ) O(n) O(n)轉(zhuǎn)移，總體復(fù)雜度需要 O ( n 2 ) O(n^2) O(n2)。

轉(zhuǎn)移方程： d p [ i ] = m a x ( d p [ i ] , d p [ j ] + s i g n ( s u m [ j + 1 , i ] ) ? ( i ? ( j + 1 ) + 1 ) ) 其 中 ( 0 ≤ j < i ) dp[i] = max(dp[i], dp[j] + sign(sum[j+1,i]) * (i-(j+1)+1)) 其中(0≤j

復(fù)雜度過高，我們考慮優(yōu)化。

根據(jù) s i g n sign sign函數(shù)的值分類討論，化簡(jiǎn)轉(zhuǎn)移方程：

d p [ i ] = m a x ( d p [ i ] , d p [ j ] + s i g n ( s u m [ i ] ? s u m [ j ] ) ? ( i ? j ) ) dp[i] = max(dp[i],dp[j]+sign(sum[i]-sum[j])*(i-j)) dp[i]=max(dp[i],dp[j]+sign(sum[i]?sum[j])?(i?j))

若 s u m [ i ] = = s u m [ j ] sum[i]==sum[j] sum[i]==sum[j], d p [ i ] = m a x ( d p [ j ] ) dp[i] = max(dp[j]) dp[i]=max(dp[j])

若 s u m [ i ] > s u m [ j ] sum[i] >sum[j] sum[i]>sum[j], d p [ i ] = m a x ( d p [ j ] ? j + i ) dp[i] = max(dp[j] - j +i) dp[i]=max(dp[j]?j+i)

若 s u m [ i ] < s u m [ j ] sum[i]< sum[j] sum[i]

我們只需要求出上述三種情況下對(duì)應(yīng)的 m a x max max，之后這三個(gè)值取 m a x max max即可。

容易發(fā)現(xiàn)，需要一個(gè)支持單點(diǎn)修改+區(qū)間查詢且復(fù)雜度過得去的數(shù)據(jù)結(jié)構(gòu)來(lái)維護(hù)。

做法是預(yù)處理前綴和，之后離散化，然后按照前綴和建線段樹（其他滿足條件的數(shù)據(jù)結(jié)構(gòu)均可）。

即線段樹的下標(biāo)表示 s u m [ j ] sum[j] sum[j],上述的三個(gè)大值分別通 q u e r y ( s u m [ i ] , s u m [ i ] ) query(sum[i],sum[i]) query(sum[i],sum[i]), q u e r y ( 1 , s u m [ i ] ? 1 ) query(1, sum[i]-1) query(1,sum[i]?1), q u e r y ( s u m [ i ] + 1 , n ) query(sum[i] + 1, n) query(sum[i]+1,n)獲得。

復(fù)雜度 O ( n l o g n ) O(nlogn) O(nlogn)。

另外，提示中試試暴力是希望先寫出暴力轉(zhuǎn)移方程，方便之后的觀察優(yōu)化。

5 e 5 5e5 5e5的數(shù)據(jù)量暴力是不可能過的。

下面給出利用線段樹優(yōu)化的代碼。

#includeusing namespace std;
typedef long long ll;
#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define itt set::iterator
#define pii pairconst int inf = 0x3f3f3f3f;
const int maxn = 5e5 + 5;
int t, n, x, h;
int sum[maxn];
int dp[maxn];
vectorvt;
struct node
{int l, r;
    int dp, dp1, dp2;//維護(hù)上述的三個(gè)大值

    int mid()
    {return (l + r) >>1;
    }

    void print()
    {cout<< l<< ' '<< r<< ' '<< dp<< ' '<< dp1<< ' '<< dp2<< '\n';
    }
} tree[maxn<<2];

void pushup(node &p, node &le, node &ri)
{p.l = le.l;
    p.r = ri.r;
    p.dp = max(le.dp, ri.dp);
    p.dp1 = max(le.dp1, ri.dp1);
    p.dp2 = max(le.dp2, ri.dp2);
}

void pushup(int p)
{pushup(tree[p], tree[p<<1], tree[p<<1|1]);
}

void build(int p, int l, int r)
{tree[p].l = l;
    tree[p].r = r;

    if(l == r)
    {tree[p].dp = tree[p].dp1 = tree[p].dp2 = -inf;
        return ;
    }

    int mid = tree[p].mid();
    build(p<<1, l, mid);
    build(p<<1|1, mid + 1, r);
    pushup(p);
}

void updata(int p, int pos, int dp, int id)
{if(tree[p].l == tree[p].r)
    {tree[p].dp = max(tree[p].dp, dp);
        tree[p].dp1 = max(tree[p].dp1, dp - id);
        tree[p].dp2 = max(tree[p].dp2, dp + id);
        return ;
    }

    int mid = tree[p].mid();
    if(pos<= mid) updata(p<<1, pos, dp, id);
    else updata(p<<1|1, pos, dp, id);
    pushup(p);
}

node query(int p, int l, int r)
{if(l >r) return {-inf, -inf, -inf, -inf};
    if(l<= tree[p].l && tree[p].r<= r) return tree[p];

    int mid = tree[p].mid();
    if(mid >= r) return query(p<<1, l, r);
    else if(mid< l) return query(p<<1|1, l, r);
    else
    {node le = query(p<<1, l, r);
        node ri = query(p<<1|1, l, r);
        node res;
        pushup(res, le, ri);
        return res;
    }
}

void work()
{vt.clear();
    cin >>n >>h;
    for(int i = 1; i<= n; ++i)
    {cin >>x;
        sum[i] = sum[i - 1] + x;
        vt.push_back(sum[i]);
        dp[i] = 0;
    }
    vt.push_back(0);

    sort(vt.begin(), vt.end());
    vt.erase(unique(vt.begin(), vt.end()), vt.end());

    build(1, 1, vt.size());

    node pp;
    int mx1, mx2, mx3, pos;
    pos = lower_bound(vt.begin(), vt.end(), 0) - vt.begin() + 1;
    updata(1, pos, 0, 0);
    for(int i = 1; i<= n; ++i)
    {pos = lower_bound(vt.begin(), vt.end(), sum[i]) - vt.begin() + 1;
        mx1 = query(1, 1, pos - 1).dp1;
        mx2 = query(1, pos, pos).dp;
        mx3 = query(1, pos + 1, vt.size()).dp2;
        dp[i] = max(mx1 + i, max(mx2, mx3 - i));
        updata(1, pos, dp[i], i);
    }

    cout<< dp[n]<< ' '<< (dp[n] >= h)<< '\n';
}

signed main()
{io;
    cin >>t;
    while(t--) work();
    return 0;
}

出題人: LYJ

出了一個(gè)bfs的模版題，沒人做，好傷心，寫了半天的題目背景，沒人看，好傷心，甚至在賽時(shí)加了一個(gè)小彩蛋，也沒人看，好傷心

雖然

n個(gè)點(diǎn)，m條邊，無(wú)向圖

給你p個(gè)起點(diǎn)，q個(gè)終點(diǎn)，問你從任意一個(gè)起點(diǎn)出發(fā)，到達(dá)任意一個(gè)終點(diǎn)需要的最短距離是多少

bfs就行，把起點(diǎn)都塞進(jìn)隊(duì)列里面，然后記錄q個(gè)終點(diǎn)，跑的時(shí)候遇到第一個(gè)出現(xiàn)的終點(diǎn)的時(shí)候就是最短的

#includeusing namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pairpii;

#define MAX 1000000 + 50
int n, m, k, x, y, a, b;
vectorG[MAX];

queueq;
setse;
int dis[MAX];

void bfs(){while(!q.empty()){int u = q.front();q.pop();
        if(se.count(u)){cout<< dis[u]<< endl;
            return;
        }
        for(auto v : G[u]){if(dis[v] != inf)continue;
            dis[v] = dis[u] + 1;
            q.push(v);
        }
    }
    cout<< "N0"<< endl;
}

void work(){cin >>n >>m;
    for(int i = 1; i<= m; ++i){cin >>x >>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    mem(dis, inf);
    cin >>a >>b;
    for(int i = 1; i<= a; ++i){cin >>x;
        q.push(x);
        dis[x] = 0;
    }
    for(int i = 1; i<= b; ++i){cin >>x;
        se.insert(x);
    }
    bfs();
    
}

int main(){work();
    return 0;
}

出題人: WWY

簽到題，沒人寫，6

我們可以把題目理解成拋硬幣，問期望拋多少次可以使得正面朝上的次數(shù)是n

顯然，期望拋2次，可以使得正面朝上的次數(shù)是1

拿n次正面朝上的期望就是2*n次

所以輸出2*n就行

這里有一個(gè)很有意思的事情：

十六分鐘的時(shí)候就有人看到了這個(gè)題，并寫出了正解，但是因?yàn)樗麤]寫輸入，所以掛了，（笑死

#pragma GCC optimize(3)
#includeusing namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pairpii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];

void work(){cin >>n;
    cout<< 2 * n<< endl;
}


int main(){io;
    work();
    return 0;
}

出題人: LYJ

出題的時(shí)候，在這個(gè)題前面出了五六個(gè)題，沒有一個(gè)簽到題，所以我就放了一個(gè)小討論題

你在0的位置，目標(biāo)是x的位置，y的位置有一個(gè)門，z的位置有一個(gè)鑰匙，問你最少需要走幾步能到x，如果不能到輸出-1

簽到題，簡(jiǎn)單分類一下就行，沒什么意思

#includeusing namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false)
#define debug(a) cout<< "Debuging...|"<< #a<< ": "<< a<< "\n";
typedef long long ll;
typedef pairpii;

#define MAX 300000 + 50
int x, y, z;

void work(){cin >>x >>y >>z;
    if(x == 0){cout<< 0<< endl;
    }
    else if(x >0){if(y< 0 || y >x)cout<< x<< endl;
        else {if(z >y)cout<< "BLEACH yyds"<< endl;
            else{if(z >0)cout<< x<< endl;
                else cout<< -z*2 + x<< endl;
            }
        }
    }
    else{if(y< x || y >0)cout<< -x<< endl;
        else{if(z< y)cout<< "BLEACH yyds"<< endl;
            else {if(z >0)cout<< 2*z - x<< endl;
                else cout<< -x<< endl;
            }
        }
    }
}


int main(){io;
    work();
    return 0;
}

出題人: DJK

給你兩個(gè)字符串 s , t s,t s,t,按照給定的操作方式，是 s s s串變成 t t t串，要求在 3 ? n 3*n 3?n次內(nèi)完成（ n n n是字符串的長(zhǎng)度）。

給出其中一種構(gòu)造方式。

我們希望當(dāng) s 串 與 t 串 s串與t串 s串與t串在位置 i i i不同時(shí)，我們希望取反第 i i i個(gè)元素且不影響其他元素，這樣就可以 O ( n ) O(n) O(n)遍歷一遍。

容易發(fā)現(xiàn)，取反和反轉(zhuǎn)都擁有一個(gè)特征。即對(duì)一個(gè)01串取反或反轉(zhuǎn)偶數(shù)次，字符串不變。

由此，我們即可實(shí)現(xiàn)取反第 i i i個(gè)位置,而不影響其他元素。

當(dāng) s 串 與 t 串 s串與t串 s串與t串在位置 i i i不同時(shí)，進(jìn)行如下操作：

• 執(zhí)行操作 i i i
• 執(zhí)行操作 1 1 1
• 執(zhí)行操作 i i i

可以發(fā)現(xiàn)，至多需要 3 ? n 3*n 3?n次，滿足題意。

代碼：

#includeusing namespace std;
typedef long long ll;
#define int ll
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define itt set::iterator
#define pii pairconst int inf = 0x3f3f3f3f;
const int maxn = 5e5 + 5;
int n;
string s, t;
int ans[3005];
int sum;

signed main()
{io;
    cin >>s >>t;

    n = s.size();
    sum = 0;
    for(int i = 0; i< n; ++i)
    {if(s[i] != t[i])
        {ans[++sum] = i + 1;
            ans[++sum] = 1;
            ans[++sum] = i + 1;
        }
    }

    cout<< sum<< ' ';
    for(int i = 1; i<= sum; ++i) cout<< ans[i]<< ' ';
    return 0;
}

從出題情況來(lái)說(shuō)，很多簽到題沒人看，沒人做，線上比賽比線下比賽的相比，差距很大，有些同學(xué)線上比賽沒人監(jiān)督，就隨便寫兩三個(gè)題就跑去玩了，這樣很不好…

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前名稱：2022SDNU-ACM結(jié)訓(xùn)賽題解-創(chuàng)新互聯(lián)
網(wǎng)址分享：http://bm7419.com/article30/gioso.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供建站公司、營(yíng)銷型網(wǎng)站建設(shè)、做網(wǎng)站、標(biāo)簽優(yōu)化、網(wǎng)站導(dǎo)航、全網(wǎng)營(yíng)銷推廣

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)