Logo syxx_zhuyile的博客

博客

IO.cpp

2026-07-16 18:55:32 By syxx_zhuyile

By @ZYLZPP

已模块化,选择需要的函数

使用方式与 cin/cout 相同

#include<bits/stdc++.h>
using namespace std;

#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
#define rFor(i, r, l) for (int i = (r); i >= (l); --i)
#define For(i, l, r) for (int i = (l); i <= (r); ++i)
typedef long long ll;
typedef double lf;
const int N = 5e5 + 5, Mo = 1e9 + 9;
inline int mo(int x) { return x -= x>=Mo? Mo: x<0? -Mo: 0; }
inline void add(int &x, const int &y) { x = mo(x + y); }
inline int ml(const int &x, const int &y) { return 1ll * x * y % Mo; }
inline void mul(int &x, const int &y) { x = ml(x, y); }
inline int qPow(int a, int b) { int r=1; for (;b;b>>=1,mul(a,a)) if (b&1) mul(r,a); return r; }
template<class C> inline bool cmax(C &x, const C &y) { return y>x? x=y, 1: 0; }
template<class C> inline bool cmin(C &x, const C &y) { return y<x? x=y, 1: 0; }

struct IO {
    //input
    char c; int f;
#define gc() getchar()
    template<class C>
    inline IO& operator >> (C &x) {
        x = 0; f = 1;
        while (!isdigit(c = gc()) && ~c) f |= -!(c ^ 45);
        while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
        x *= f; return *this;
    }//整型
    inline IO& operator >> (char &x) {
        while ((c = gc()) < 33 && ~c);
        x = c; return *this;
    }//字符
    inline IO& operator >> (char *x) {
        while ((c = gc()) < 33 && ~c);
        while (c > 32) *x++ = c, c = gc();
        *x = 0; return *this;
    }//字符串
    inline IO& operator >> (double &x) {
        double p(1); x = 0; f = 1;
        while (!isdigit(c = gc()) && ~c) f |= -!(c ^ 45);
        while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
        if (!(c ^ 46)) while (isdigit(c = gc())) x += (c ^ 48) * (p /= 10);
        x *= f; return *this;
    }//double

    //output
    int st[66], t;
#define pc(c) putchar(c)
    template<class C>
    inline IO& operator << (C x) {
        if (!x) pc('0'); if (x < 0) pc('-'), x = -x;
        while (x) st[++t] = x % 10, x /= 10;
        while (t) pc(st[t--] ^ 48);
        return *this;
    }//整型
    inline IO& operator << (char x) {
        pc(x); return *this;
    }//字符
    template<class C>
    inline IO& operator << (C *x) {
        while (*x) pc(*x++);
        return *this;
    }//字符串
    inline bool operator ~ () const { return ~c; } //判断是否文件未结束 文件结束时c==EOF==-1
} io;

int main() {
    char a[45];
    scanf("%s", a);
    io << a;
    io << "123";
    return 0;
}
//2024.8.10_

#2430. [COCI2022-2023#1] Neboderi

2026-07-16 16:43:57 By syxx_zhuyile

By @ZYLZPP

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define rFor(i, r, l) for (int i = (r); i >= (l); --i)
#define For(i, l, r) for (int i = (l); i <= (r); ++i)
typedef long long ll;
const int N = 1e6 + 5;
template<class C> inline bool cmax(C &x, const C &y) { return y>x? x=y, 1: 0; }

struct IO {
    char c; int f;
#define gc() getchar()
    template<class C>
    inline IO& operator >> (C &x) {
        x = 0; f = 1;
        while (!isdigit(c = gc()) && ~c) f |= -!(c ^ 45);
        while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
        x *= f; return *this;
    }
    inline bool operator ~ () const { return ~c; }
} io;

int n, K, a[N];
ll s[N], ans;
vector<int > q;

int main() {
    io >> n >> K;
    For (i, 1, n) io >> a[i], s[i] = s[i - 1] + a[i];
    For (i, 1, n) {
        q.pb(i);
        for (auto &x : q) a[x] = __gcd(a[x], a[i]);
        vector<int > p; int lst = 0;
        for (auto &x : q) if (a[x] > lst) p.pb(x), lst = a[x], cmax(ans, (i - x + 1 >= K) * (s[i] - s[x - 1]) * lst);
        swap(p, q);
    }
    printf("%lld", ans);

    return 0;
}

#2424. [COCI 2023/2024 #5] Rolete

2026-07-16 11:39:19 By syxx_zhuyile

By @封禁用户

首先显然要求出询问为任意值时的答案然后查询就好。我们通过大眼观察法可以得到一个贪心:求 $x$ 的答案,就在 $x+1$ 的最优方案基础上操作,把高出部分一个一个拉上去(称为操作 $1$)和整体下降(称为操作 $2$)的花费做一个比较,选代价更小的那个。

这题的难点其实并非贪心,而是思考这个看起来就很假的贪心的正确性。考虑反证法。

如果你 $x+1$ 的情况用这种方法得到了最优解,并且 $x$ 的时候用这种方法得不到最优解,那么你一定是因为调整上面的某一步操作会让之前的代价更大但是此时的代价最小。

显然如果会这样要么是之前用 $1$ 代价更大但是如果用 $1$ 可以减小本次使用 $2$ 操作的代价,但是如果你之前用 $2$ 现在用 $1$ 的操作代价是一样的,所以你之前用 $2$ 是不劣的。

或者是之前用 $2$ 代价更大但是用 $2$ 操作可以拉下去一些本来不需要拉的窗帘,让你 $1$ 操作的代价更小。但是你之前用 $1$ 这下用 $2$ 肯定也是不劣的。

综上,你照这样贪心下去肯定是不劣的,那么代码也非常简单啊。

#include<bits/stdc++.h>
#define int long long
 #define endl '\n'
using namespace std;
const int mod=998244353,inf=0x3f3f3f3f3f3f3f3f;
const int N=1e5+10,M=2e5+10;
const int m=1e5;
int n,t,s,k;
int a[N],ans[N],cnt[N];
int sl[N],sr[N];
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >>n >> t >> s >> k;
    for ( int i = 1 ; i <= n ; i++ )cin >> a[i];
    for ( int i = 1 ; i <= n ; i++ )sl[a[i]]++,sr[a[i]]++;
    for ( int i = 1 ; i <= m ; i++ )sl[i]+=sl[i-1];
    for ( int i = m ; i >= 0 ; i-- )sr[i]+=sr[i+1];
    for ( int i = m-1 ; i >= 0 ; i-- )
    {
        int cost1=s+k*sl[cnt[i+1]];
        int cost2=sr[i+1+cnt[i+1]]*t;
        if(cost1<cost2)ans[i]=ans[i+1]+cost1,cnt[i]=cnt[i+1]+1;
        else ans[i]=ans[i+1]+cost2,cnt[i]=cnt[i+1];
    }
//    for ( int i = 0 ; i <= 6 ; i++ )
//        cout << ans[i] << " " << cnt[i] << endl;
    int q;cin >>q;
    while(q--){int x;cin >> x;cout << ans[x] << " ";}
    return 0;
}

#2420. [COCI 2023/2024 #4] Roboti

2026-07-15 11:28:43 By syxx_zhuyile

By @ZYLZPP

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(a) a.begin(), a.end()
#define rFor(i, r, l) for (int i = (r); i >= (l); --i)
#define For(i, l, r) for (int i = (l); i <= (r); ++i)
const int N = 1e6 + 5;
inline void cmin(int &x, const int &y) { y<x? x=y: 0; }

struct IO {
    char c; int f;
#define gc() getchar()
    template<class C>
    inline IO& operator >> (C &x) {
        x = 0; f = 1;
        while (!isdigit(c = gc()) && ~c) f |= -!(c ^ 45);
        while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
        x *= f; return *this;
    }
    inline bool operator ~ () const { return ~c; }
} io;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
int n, m, K, q, b[N], fa[N], dep[N], co[N], tot, len[N], ans, U[4], V[4];
vector<array<int, 2 > > a[2][N];

inline int find(int x, int y, int d) {
    int c = d & 1; if (!c) swap(x, y);
    if (a[c][x].empty()) return -1;
    array<int, 2 > p = {y, d<2? 0: K};
    auto it = lower_bound(all(a[c][x]), p);
    if (d < 2) it==a[c][x].begin()? it = a[c][x].end() - 1: it--;
    else if (it == a[c][x].end()) it = a[c][x].begin();
    return (*it)[1] << 2 | d;
}

inline int dfs(int u, int pre) {
    co[u] = tot; dep[u] = dep[pre] + 1;
    return co[fa[u]]? dep[u]: dfs(fa[u], u);
}

inline int dis(int u, int v) {
    if (co[u] ^ co[v]) return K + 1;
    int d = len[co[u]];
    return (dep[v] - dep[u] + d) % d;
}

int main() {
    io >> n >> m >> K;
    int x, y, X, Y; char op[3];
    For (i, 0, K - 1) {
        io >> x >> y; scanf("%s", op);
        b[i] = op[0]=='L'? 1: 3;
        a[0][y].pb({x, i}); a[1][x].pb({y, i});
    }
    K *= 4;
    For (i, 1, n) sort(all(a[1][i]));
    For (i, 1, m) sort(all(a[0][i]));
    For (x, 1, n) for (auto &[y, id] : a[1][x]) For (k, 0, 3) fa[id << 2 | k] = find(x, y, (k + b[id]) % 4);
    For (i, 0, K - 1) if (!co[i]) tot++, len[tot] = dfs(i, i);
    io >> q;
    while (q--) {
        ans = K + 1;
        io >> x >> y >> X >> Y;
        For (k, 0, 3) U[k] = find(x, y, k), V[k] = find(X - dx[k], Y - dy[k], k);
        For (i, 0, 3) if (~U[i]) For (j, 0, 3) if (~V[j]) cmin(ans, dis(U[i], V[j]));
        if ((x == X && a[1][x].empty()) || (y == Y && a[0][y].empty())) ans = 0;
        printf("%d\n", ans<=K? ans: -1);
    }

    return 0;
}

#2418. [COCI 2023/2024 #4] Lepeze

2026-07-15 10:38:25 By syxx_zhuyile

By @AFewSuns

#include<bits/stdc++.h>
using namespace std;
using namespace my_std;
#define mod 1000000007
ll n,q,jc[200020],jcinv[200020],invv[200020],sum[200020],tree[200020];
il ll lowbit(ll x){
    return x&(-x);
}
il void mdf(ll x,ll v){
    if(v<0) v=-v;
    else v=invv[v];
    while(x<=n){
        tree[x]=tree[x]*v%mod;
        x+=lowbit(x);
    }
}
il ll query(ll x){
    ll res=1;
    while(x){
        res=res*tree[x]%mod;
        x-=lowbit(x);
    }
    return res;
}
il void solve(ll x,ll y,ll t){
    sum[x]-=t;
    ll len=(y-x+n)%n-1;
    swap(x,y);
    x=x%n+1;
    y=(y+n-2)%n+1;
    if(x<=y){
        mdf(x,t*len);
        mdf(y+1,-t*len);
    }
    else{
        mdf(x,t*len);
        mdf(1,t*len);
        mdf(y+1,-t*len);
    }
}
int main(){
    n=read();
    q=read();
    jc[0]=1;
    fr(i,1,n) jc[i]=jc[i-1]*i%mod;
    jcinv[n]=inv(jc[n],mod);
    pfr(i,n-1,0) jcinv[i]=jcinv[i+1]*(i+1)%mod;
    fr(i,1,n) invv[i]=jcinv[i]*jc[i-1]%mod;
    fr(i,1,n) sum[i]=n-3;
    fr(i,1,n) tree[i]=1;
    fr(i,1,n-3){
        ll x=read(),y=read();
        solve(x,y,1);
        solve(y,x,1);
    }
    while(q--){
        ll opt=read();
        if(opt==1){
            ll x=read(),y=read(),xx=read(),yy=read();
            solve(x,y,-1);
            solve(y,x,-1);
            solve(xx,yy,1);
            solve(yy,xx,1);
        }
        else{
            ll x=read();
            pf("%lld %lld\n",sum[x],jc[sum[x]]*query(x)%mod);
        }
    }
}
syxx_zhuyile Avatar