因为考试过多，所以学校的博客就暂时咕掉了，放到家里来写

不过话说，vscode的markdown编辑器还是真的很好用

先把 \(noip\) 模拟 \(23\) 的总结写了吧。。

俗话说：“连胜之后必是连败，连败之后必是连胜”。

经过之前连续五场比赛的挂分，终于回来了一点点。。。

菜我还是。。。

咱也不知道当时的零分是怎么考出来的。。。。

\(\color{green}{\huge{\text{菜}}}\)

。。。。。。。。

好吧。。。。。。

每次考爆炸的时候在赛后总会发现自己的题目还是没有审清楚。

然后懊悔好长时间。。。。。

我的语文分数似乎也不是很低啊

所以我在此立下 \(flag\)

以后一个题目不读十遍我就不动键盘。。。

不然想的再快也是浪费时间。。。。

联:

这个题目说白了就是一个线段树的板子题目。。

然而恶心的出题人把范围开到了很大很大。。

但是 \(oj\) 上的题目却是没有截到那个最为重要的信息。

然后很多巨佬就 \(gg\) 了。

惨.jpg

这么大的区间所以一定要进行 离散化

然后开始愉快的线段树。

简简单单。。

#include<bits/stdc++.h>
using std::cout; using std::endl;
#define int long long
#define debug cout<<"debug"<<endl
namespace xin_io
{
    #define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
    #define scanf a14 = scanf
    char buf[1<<20],*p1 = buf,*p2 = buf; FILE *xinnb1; typedef long long ll; int a14;
    void openfile() {xinnb1 = freopen("t.txt","r",stdin);} void outfile() {xinnb1 = freopen("o.txt","w",stdout);}
    inline int get()
    {
        int s = 0,f = 1; register char ch = gc();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = gc();}while(isdigit(ch))  {s = s * 10 + ch - '0'; ch = gc();}
        return s * f;
    }
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 0x7f7f7f7f7f7f7f;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
namespace xin
{
    class xin_query{public:int ty,l,r;}q[maxn];
    int m,n;
    int a[maxn*10],zhi = 0;
    std::map<int,int> lisan;
    class xin_segment
    {
    private:
        #define ls(x) (x << 1)
        #define rs(x) (x << 1 | 1)
        inline void up(int x)
        {
//            debug;
            t[x].s = std::min(t[ls(x)].s,t[rs(x)].s);
            if(t[ls(x)].st == t[rs(x)].st) t[x].st = t[ls(x)].st;
            else t[x].st = -1;
        }
        inline void down(int x,int l,int r)
        {
            if(t[x].debt == -1)return;
            register int mid = l + r >> 1;
            t[ls(x)].debt = t[rs(x)].debt = t[ls(x)].st = t[rs(x)].st = t[x].debt;
            if(!t[ls(x)].st) t[ls(x)].s = l;
            else t[ls(x)].s = inf;
            if(!t[rs(x)].st)t[rs(x)].s = mid+1;
            else t[rs(x)].s = inf;
            t[x].debt = -1;
        }
    public:
        class xin_tree
        {
            public:
                int st,s,debt;
        }t[maxn];
        void build(int x,int l,int r)
        {
            t[x].s = inf; t[x].debt = -1;
            if(l == r){t[x].s = l; return;}
            register int mid = l + r >> 1;
            build(ls(x),l,mid); build(rs(x),mid+1,r);
            up(x);
        }
        void modify(int x,int l,int r,int ql,int qr,int opt)
        {
            if(qr < l or r < ql)return;
            if(ql <= l and r <= qr and t[x].st != -1)
            {
                if(opt == 1) t[x].st = t[x].debt = 1;
                else if(opt == 2) t[x].st = t[x].debt = 0;
                else if(opt == 3) t[x].st ^= 1,t[x].debt = t[x].st;
                if(!t[x].st) t[x].s = l; else t[x].s = inf;
                return;
            }
            register int mid = l + r >> 1;
            down(x,l,r);
            modify(ls(x),l,mid,ql,qr,opt); modify(rs(x),mid+1,r,ql,qr,opt);
            up(x);
        }
    }t;
    inline short main()
    {
    #ifndef ONLINE_JUDGE
        openfile();
    #endif
        m = get();
        try(i,1,m)
        {
            q[i].ty = get(); q[i].l = get(); q[i].r = get();
        }
        try(i,1,m)  a[++zhi] = q[i].l,a[++zhi] = q[i].r, a[++zhi] = q[i].l + 1, a[++zhi] = q[i].r + 1;
        a[++zhi] = 1;
//        try(i,1,zhi) cout<<a[i]<<endl;
//        cout<<"zhi  =  "<<zhi<<endl;
        std::sort(a + 1,a + zhi + 1); n = std::unique(a + 1,a + zhi + 1) - (a + 1);
        try(i,1,m)
        {
            register int pos1 = std::lower_bound(a+1,a+n+1,q[i].r+1) - a,pos2 = std::lower_bound(a+1,a+n+1,q[i].l+1) - a;
            lisan[pos1] = q[i].r+1; lisan[pos2] = q[i].l+1;
//            cout<<"pos1 = "<<pos1<<" pos2 = "<<pos2<<endl;
            register int temp = q[i].l;
            q[i].l = std::lower_bound(a+1,a+n+1,q[i].l)-a; lisan[q[i].l] = temp;
            temp = q[i].r;
            q[i].r = std::lower_bound(a+1,a+n+1,q[i].r)-a; lisan[q[i].r] = temp;
        }
        lisan[1] = 1; t.build(1,1,n);
        try(i,1,m)
        {
            t.modify(1,1,n,q[i].l,q[i].r,q[i].ty);
            printf("%lld\n",lisan[t.t[1].s]);
        }
//        cout<<"Mem = "<<sizeof(t.t) / (1 << 20)<<" MB"<<endl;
        return 0;
    }
}
signed main() {return xin::main();}

赛:

这个题目就是一个其实不是很难的贪心。。

我们将这个所有的物品分成四个大类。

1. 这个类别就是两个人 \(a\) 和 \(b\) 都喜欢的。

2. 这个是 \(a\) 单独喜欢的。

3. 这个是 \(b\) 单独喜欢的。

4. 这个是 \(a\) 和 \(b\) 都不喜欢的。

这样一来不重不漏。。。

然后我们设选择 \(1\) 类别的选了 \(x\) 个

然后 \(2\) 和 \(3\) 就是 \(k-x\) 个。

然后再从剩下没选的地方中选择，满足一共正好 \(m\) 个。

然后我们要做的工作就是枚举 \(m\)。

然后每次更新答案。

就这。。

然而考场上就莽了一个 \(XIN\) 队。。

惭愧。

#include<bits/stdc++.h>
using std::cout; using std::endl;
#define int long long
#define debug cout<<"debug"<<endl
namespace xin_io
{
    #define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
    char buf[1<<20],*p1 = buf,*p2 = buf; FILE *xinnb1; typedef long long ll;
    void openfile() {xinnb1 = freopen("t.txt","r",stdin);} void outfile() {xinnb1 = freopen("o.txt","w",stdout);}
    inline int get()
    {
        int s = 0,f = 1; register char ch = gc();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = gc();}while(isdigit(ch))  {s = s * 10 + ch - '0'; ch = gc();}
        return s * f;
    }
}
using namespace xin_io; static const int maxn = 1e6+10,inf = 0x7f7f7f7f7f7f7f7f;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
namespace xin
{
    int a1[maxn],cnt1,a2[maxn],cnt2,a3[maxn],cnt3,a4[maxn],cnt4;
    int he1[maxn],he2[maxn],he3[maxn],he4[maxn];
    int n,m,k;
    int val[maxn],numa,numb;
    bool visa[maxn],visb[maxn];
    int lj[maxn],cntl = 0;
    inline short main()
    {
    #ifndef ONLINE_JUDGE
        openfile();
    #endif
        n = get(); m = get(); k = get();
        try(i,1,n) val[i] = get();
        numa = get();
        try(i,1,numa)
        {
            register int x = get();
            visa[x] = 1;
        }
        numb = get(); bool sp1 = 1;
        try(i,1,numb)
        {
            register int x = get();
            visb[x] = 1;
            if(visa[x]) sp1 = 0;
        }
        if(sp1 and 2 * k > m) {cout<<-1<<endl; return 0;}
        try(i,1,n)
        {
            if(visa[i] and visb[i]) a1[++cnt1] = val[i];
            else if(visa[i] and !visb[i]) a2[++cnt2] = val[i];
            else if(!visa[i] and visb[i]) a3[++cnt3] = val[i];
            else a4[++cnt4] = val[i];
        }
        std::sort(a1+1,a1+cnt1+1); std::sort(a2+1,a2+cnt2+1);
        std::sort(a3+1,a3+cnt3+1); std::sort(a4+1,a4+cnt4+1);
        try(i,1,cnt1) he1[i] = he1[i-1] + a1[i]; try(i,1,cnt2) he2[i] = he2[i-1] + a2[i];
        try(i,1,cnt3) he3[i] = he3[i-1] + a3[i]; try(i,1,cnt4) he4[i] = he4[i-1] + a4[i];
        int ans = inf;
        register int ms = std::min(k,std::min(m,cnt1));
        if(!ms)
        {
            register int temp = he2[k] + he3[k];
            try(i,k+1,cnt2) lj[++cntl] = a2[i]; try(i,k+1,cnt3) lj[++cntl] = a3[i];
            try(i,1,cnt4) lj[++cntl] = a4[i];
            std::sort(lj+1,lj+cntl+1);
            try(i,1,m-2*k) temp += lj[i];
            cout<<temp<<endl;
            return 0;
        }
        try(i,0,ms)
        {
            if((2 * k - i > m) or (k - i) > cnt2 or (k - i) > cnt3) continue;
            register int temp = he1[i] + he2[k-i] + he3[k-i],tot = 2 * k - i;
//            cout<<"i = "<<i<<" he1[i] = "<<he1[i]<<" he2[i] = "<<he2[i]<<" he3[i] = "<<he3[i]<<endl;
            if(tot < m) temp += he4[m - 2 * k + i];
            ans = std::min(ans,temp);
        }
//        if(!ms) debug;
        cout<<ans<<endl;
        return 0;
    }
}
signed main() {return xin::main();}

题:

这个题目实际上还是比较简单。

其实就是我们设定一个集合，之后从后面开始向前枚举这个集合。

然后计算

注意去重

代码非常短

%: pragma GCC optimize("O9")
#include<bits/stdc++.h>
using std::cout; using std::endl;
#define debug cout<<"debug"<<endl
namespace xin_io
{
    #define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++
    char buf[1<<20],*p1 = buf,*p2 = buf; FILE *xinnb1; typedef long long ll;
    void openfile() {xinnb1 = freopen("t.txt","r",stdin);} void outfile() {xinnb1 = freopen("o.txt","w",stdout);}
    inline int get()
    {
        int s = 0,f = 1; register char ch = gc();
        while(!isdigit(ch)) {if(ch == '-') f = -1; ch = gc();}while(isdigit(ch))  {s = s * 10 + ch - '0'; ch = gc();}
        return s * f;
    }
}
using namespace xin_io; static const int maxn = 1e3+10,inf = 0x7f7f7f7f;
#define try(i,a,b) for(register signed i=a;i<=b;++i)
#define throw(i,a,b) for(register signed i=a;i>=b;--i)
namespace xin
{
    int f[maxn][maxn],g[maxn*100];
    int n,m,u[maxn*100],v[maxn*100],ans;
    inline short main()
    {
    #ifndef ONLINE_JUDGE
        openfile();
    #endif
        n = get(); m = get();
        try(i,1,m) u[i] = get(),v[i] = get();
        try(i,1,n) f[i][i] = 1,g[i] = 1;
        try(j,1,n)
        {
            throw(i,m,1)
            {
                register int x = u[i],y = v[i];
                if(f[j][x] and f[j][y]) g[j] = 0;
                else if(f[j][x]) f[j][y] = 1;
                else if(f[j][y]) f[j][x] = 1;
            }
        }
        try(i,1,n)
            try(j,i+1,n)
            {
                if(!g[i] or !g[j]) continue;
                bool ok = 1;
                try(k,1,n) if(f[i][k] and f[j][k]) {ok = 0; break;}
                ans += ok;
            }
        cout<<ans<<endl;
        return 0;
    }
}
signed main() {return xin::main();}