注：本篇不存在任何性别歧视，请放心阅读。

你们有没有发现，OIer绝大部分都是男生？

我现在在贵州省安顺市，陪我弟打百灵杯（全国围棋少儿公开赛）

和信息与未来不同的是，参赛选手男女比例很协调。。。

就很离谱啊，毕竟都是智力运动。。。

上来先一波@@

@Joker @xushuoxin @昊然 @Andy0815

好久没看，昨天打卡题一看，最小生成树，虽然挺水的，但是还是没想到各位进步这么快

我们开学都要被 @阿兹卡班的小天狼星 单手吊打了。。。这可能是事实。

不信？想必各位现在一定在学图论吧，哈希表学了吗？字符串哈希？单源最短路径，树状数组，rmq，状压dp，双端搜索，记忆化搜索，单调队列，单调栈？

所以，开学就等着被王昊宸单手吊打吧！！！

悬赏洛谷P3373，悬赏3个样例（任意）；

一下是题面（量力而行）；

【模板】线段树 2

题目描述

如题，已知一个数列，你需要进行下面三种操作：

• 将某区间每一个数乘上 $x$；
• 将某区间每一个数加上 $x$；
• 求出某区间每一个数的和。

输入格式

第一行包含三个整数 $n,q,m$，分别表示该数列数字的个数、操作的总个数和模数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $q$ 行每行包含若干个整数，表示一个操作，具体如下：

操作 $1$： 格式：1 x y k 含义：将区间 $[x,y]$ 内每个数乘上 $k$

操作 $2$： 格式：2 x y k 含义：将区间 $[x,y]$ 内每个数加上 $k$

操作 $3$： 格式：3 x y 含义：输出区间 $[x,y]$ 内每个数的和对 $m$ 取模所得的结果

输出格式

输出包含若干行整数，即为所有操作 $3$ 的结果。

样例 #1

样例输入 #1

5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4

样例输出 #1

17
2

提示

【数据范围】

对于 $30\%$ 的数据：$n \le 8$，$q \le 10$。
对于 $70\%$ 的数据：$n \le 10^3 $，$q \le 10^4$。
对于 $100\%$ 的数据：$1 \le n \le 10^5$，$1 \le q \le 10^5$。

除样例外，$m = 571373$。

（数据已经过加强 ^_^）

故输出应为 $17$、$2$（$40 \bmod 38 = 2$）。

以上是题面

首先给出ACcode和清晰题解者将获得免费的三个样例（我给）。

主要在区间乘法的地方不知道怎么做。大家可以看看我P3372线段数1的代码：

#include<iostream>
#include<cmath>
#define int long long
using namespace std;
int n,m;
int mov,x,y,k;
struct node{
    int left;
    int right;
    int sum;
    int l,r;
    int lazy;
}tree[400005];
int num[100005];
inline int read(){
    int ret=1,k=0;
    char c=getchar();
    while(c<'0' or c>'9'){if(c=='-'){ret = -1;}c=getchar();}
    while(c>='0' and c<='9'){k=k*10+c-'0';c=getchar();}
    return ret*k;
}
inline void write(int n){
    if(n>9){
        write(n/10);
    }
    putchar(n%10+'0');
}
int build(int pos,int l,int r){
    if(l==r){
        tree[pos].l=l;
        tree[pos].r=r;
        tree[pos].sum=num[(l+r)/2];
        return num[(l+r)/2];
    }
    int a=build(pos*2,l,(l+r)/2);
    int b=build(pos*2+1,(l+r)/2+1,r);
    tree[pos].left=pos*2;
    tree[pos].right=pos*2+1;
    tree[pos].sum=a+b;
    tree[pos].l=l;
    tree[pos].r=r;
    return a+b;
}

void push_down(int x)
{
    if(tree[x].lazy == 0) return;
    int le = tree[x].left, ri = tree[x].right, lz = tree[x].lazy;
    tree[le].lazy += lz, tree[ri].lazy += lz;
    tree[le].sum += lz * (tree[le].r - tree[le].l + 1);
    tree[ri].sum += lz * (tree[ri].r - tree[ri].l + 1);
    tree[x].lazy = 0;
} 

void add(int pos){
    if(tree[pos].l > y || tree[pos].r < x) return; 
    if((x<=tree[pos].l and y>=tree[pos].r)){
        tree[pos].lazy+=k;
        tree[pos].sum+=(tree[pos].r-tree[pos].l + 1)*k;
        return;
    }
//    if(tree[pos].lazy>0){
//        tree[tree[pos].left].lazy+=tree[pos].lazy,tree[tree[pos].left].sum+=tree[tree[pos].left].lazy*(tree[tree[pos].left].r-tree[tree[pos].left].l + 1);
//        tree[tree[pos].right].lazy+=tree[pos].lazy,tree[tree[pos].right].sum+=tree[tree[pos].right].lazy*(tree[tree[pos].right].r-tree[tree[pos].right].l + 1);
//        tree[pos].lazy=0;
//    }
    push_down(pos);
    add(tree[pos].left);//递归下降
    add(tree[pos].right);//递归下降
    tree[pos].sum = tree[tree[pos].left].sum + tree[tree[pos].right].sum;
}
int ask(int pos){
    if(tree[pos].l > y || tree[pos].r < x) return 0; 
    if((x<=tree[pos].l and y>=tree[pos].r)){
        return tree[pos].sum;
    }
//    if(tree[pos].lazy>0){
//        tree[tree[pos].left].lazy+=tree[pos].lazy,tree[tree[pos].left].sum+=tree[tree[pos].left].lazy*(tree[tree[pos].left].r-tree[tree[pos].left].l + 1);
//        tree[tree[pos].right].lazy+=tree[pos].lazy,tree[tree[pos].right].sum+=tree[tree[pos].right].lazy*(tree[tree[pos].right].r-tree[tree[pos].right].l + 1);
//        tree[pos].lazy=0;
//    }
    push_down(pos);
    int ret=0;
    ret+=ask(tree[pos].left);//递归下降
    ret+=ask(tree[pos].right);//递归下降
    return ret;
}
signed main(){
    n=read();
    m=read();
    for(int i = 1;i <= n;i++){
        num[i]=read();
    }
    build(1,1,n);

    while(m--){
        mov=read();
        if(mov==1){
            x=read(),y=read(),k=read();
            add(1);
        }else{
            x=read(),y=read();
            write(ask(1));
            putchar('\n');
        }
    }
    return 0;
}

以上我没有抄题解。我自己写的。

这是P3372的代码。求P3373思路和ACcode!!!

题号：P2482

[SDOI2010] 猪国杀

题目描述

游戏背景

《猪国杀》是一种多猪牌类回合制游戏，一共有 $3$ 种角色：主猪，忠猪，反猪。每局游戏主猪有且只有 $1$ 只，忠猪和反猪可以有多只，每只猪扮演 $1 $ 种角色。

游戏目的

主猪 / $\texttt{MP}$：自己存活的情况下消灭所有的反猪。
忠猪 / $\texttt{ZP}$：不惜一切保护主猪，胜利条件与主猪相同。
反猪 / $\texttt{FP}$：杀死主猪。

游戏过程

游戏开始时，每个玩家手里都会有 $4$ 张牌，且体力上限和初始体力都是 $4$ 。

开始游戏时，从主猪开始，按照逆时针方向（数据中就是按照编号从 $ 1 , 2, 3 \ldots n , 1 \ldots $ 的顺序）依次行动。

每个玩家自己的回合可以分为 2 个阶段：

• 摸牌阶段：从牌堆顶部摸 $2$ 张牌，依次放到手牌的最右边；
• 出牌阶段：你可以使用任意张牌，每次使用牌的时候都使用最靠左的能够使用的牌。当然，要满足如下规则：
  1. 如果没有猪哥连弩，每个出牌阶段只能使用 $1$ 次「杀」来攻击；
  2. 任何牌被使用后被弃置（武器是装备上）；被弃置的牌以后都不能再用，即与游戏无关。

各种牌介绍

每张手牌用 $1$ 个字母表示，字母代表牌的种类。

基本牌

• 『桃 / $\texttt{P}$』在自己的回合内，如果自己的体力值不等于体力上限，那么使用 $1$ 个桃可以为自己补充 $1$ 点体力，否则不能使用桃；桃只能对自己使用；在自己的回合外，如果自己的血变为 $0$ 或者更低，那么也可以使用。

• 『杀 / $\texttt{K}$』在自己的回合内，对攻击范围内除自己以外的 $1$ 名角色使用。如果没有被『闪』抵消，则造成 $1$ 点伤害。无论有无武器，杀的攻击范围都是 $1$。

• 『闪 / $\texttt{D}$』当你受到杀的攻击时，可以弃置 $1$ 张闪来抵消杀的效果。

锦囊牌

• 『决斗 / $\texttt{F}$』出牌阶段，对除自己以外任意 $1$ 名角色使用，由目标角色先开始，自己和目标角色轮流弃置 $1$ 张杀，首先没有杀可弃的一方受到 $1$ 点伤害，另一方视为此伤害的来源。

• 『南猪入侵 / $\texttt{N}$』出牌阶段，对除你以外所有角色使用，按逆时针顺序从使用者下家开始依次结算，除非弃置 $1$ 张杀，否则受到 $1$ 点伤害。

• 『万箭齐发 / $\texttt{W}$』和南猪入侵类似，不过要弃置的不是杀而是闪。

• 『无懈可击 / $\texttt{J}$』在目标锦囊生效前抵消其效果。每次有 $1$ 张锦囊即将生效时，从使用这张锦囊的猪开始，按照逆时针顺序，依次得到使用无懈可击的机会；效果：用于决斗时，决斗无效并弃置；用于南猪入侵或万箭齐发时，当结算到某个角色时才能使用，当前角色不需弃置牌并且不会受到伤害（仅对 $1$ 个角色产生效果）；用于无懈可击时，成为目标的无懈可击被无效。

装备牌

• 『猪哥连弩 / $\texttt{Z}$』武器，攻击范围 $1$ ，出牌阶段你可以使用任意张杀; 同一时刻最多只能装 $1$ 把武器；如果先前已经有了 $1$ 把武器，那么之后再装武器的话，会弃置以前的武器来装现在的武器。

特殊事件及概念解释

• 伤害来源：杀、南猪入侵、万箭齐发的伤害来源均是使用该牌的猪，决斗的伤害来源如上；

• 距离：两只猪的距离定义为沿着逆时针方向间隔的猪数 $+1$ 。即初始时 $1$ 和 $2$ 的距离为 $1$ ，但是 $2$ 和 $1$ 的距离就是 $n-1$ 。注意一个角色的死亡会导致一些猪距离的改变；

• 玩家死亡：如果该玩家的体力降到 $0$ 或者更低，并且自己手中没有足够的桃使得自己的体力值回到 $1$ ，那么就死亡了，死亡后所有的牌（装备区，手牌区）被弃置；

• 奖励与惩罚：反猪死亡时，最后一个伤害来源处（即使是反猪）立即摸 $3$ 张牌。忠猪死亡时，如果最后一个伤害来源是主猪，那么主猪所有装备牌、手牌被弃置。

注意：一旦达成胜利条件，游戏立刻结束，因此即使会摸 $3$ 张牌或者还有牌可以用也不用执行了。

现在，我们已经知道每只猪的角色、手牌，还有牌堆初始情况，并且假设每个角色会按照如下的行为准则进行游戏，你需要做的就是告诉小猪 iPig 最后的结果。

几种行为

• 献殷勤：使用无懈可击挡下南猪入侵、万箭齐发、决斗；使用无懈可击抵消表敌意；
• 表敌意：对某个角色使用杀、决斗；使用无懈可击抵消献殷勤；
• 跳忠：即通过行动表示自己是忠猪。跳忠行动就是对主猪或对某只已经跳忠的猪献殷勤，或者对某只已经跳反的猪表敌意；
• 跳反：即通过行动表示自己是反猪。跳反行动就是对主猪或对某只已经跳忠的猪表敌意，或者对某只已经跳反的猪献殷勤。

注意：忠猪不会跳反，反猪也不会跳忠；不管是忠猪还是反猪，能够跳必然跳。

行动准则

共性

• 每个角色如果手里有桃且生命值未满，那么必然吃掉；
• 有南猪入侵、万箭齐发、必然使用；有装备必然装上；
• 受到杀时，有闪必然弃置；
• 响应南猪入侵或者万箭齐发时候，有杀 / 闪必然弃置；
• 不会对未表明身份的猪献殷勤（包括自己）。

特性

• 主猪：
  • 主猪会认为「没有跳身份，且用南猪入侵 / 万箭齐发对自己造成伤害的猪」是类反猪（没伤害到不算，注意类反猪并没有表明身份），如果之后跳了，那么主猪会重新认识这只猪；
  • 对于每种表敌意的方式，对逆时针方向能够执行到的第一只类反猪或者已跳反猪表；如果没有，那么就不表敌意；
  • 决斗时会不遗余力弃置杀；
  • 如果能对已经跳忠的猪或自己献殷勤，那么一定献；如果能够对已经跳反的猪表敌意，那么一定表。
• 忠猪：
  • 对于每种表敌意的方式，对「逆时针方向能够执行到的第一只已经跳反的猪」表，如果没有，那么就不表敌意；
  • 决斗时，如果对方是主猪，那么不会弃置杀，否则，会不遗余力弃置杀；
  • 如果有机会对主猪或者已经跳忠的猪献殷勤，那么一定献。
• 反猪：
  • 对于每种表敌意的方式，如果有机会则对主猪表，否则，对「逆时针方向能够执行到的第一只已经跳忠的猪」表，如果没有，那么就不表敌意；
  • 决斗时会不遗余力弃置杀；
  • 如果有机会对已经跳反的猪献殷勤，那么一定献。

限于 iPig 只会用 P++ 语言写 A + B，他请你用 Pigcal (Pascal)、P (C) 或 P++ (C++) 语言来帮他预测最后的结果。

输入格式

输入文件第一行包含两个正整数 $ n $ $ (2 \leqslant n \leqslant 10) $ 和 $m$ $ (m \leqslant 2000) $，分别代表玩家数和牌堆中牌的数量。数据保证牌的数量够用。

接下来 $n$ 行，每行 $5$ 个字符串，依次表示对第 $i$ 只猪的角色和初始 $4 $ 张手牌描述。编号为 $1$ 的肯定是主猪。

再接下来一行，一共 $m$ 个字符串，按照从牌堆顶部到牌堆底部的顺序描述每张牌。

注意：所有的相邻的两个字符串都严格用 $1$ 个空格隔开，行尾没有多余空格。

输出格式

输出数据第一行包含一个字符串代表游戏结果。如果是主猪胜利，那么输出 $\texttt{MP}$ ，否则输出 $\texttt{FP}$ 。数据保证游戏总会结束。

接下来 $n$ 行，第 $i$ 行是对第 $i$ 只猪的手牌描述（注意只需要输出手牌），按照手牌从左往右的顺序输出，相邻两张牌用 $1$ 个空格隔开，行末尾没有多余空格。如果这只猪已阵亡，那么只要输出 $\texttt{DEAD}$ 即可。

注意：如果要输出手牌而没有手牌的话，那么只需输出 $1$ 个空行。

由于数据问题，若牌堆已空，按照每次抽牌抽到的都是最后一张。

样例 #1

样例输入 #1

3 10
MP D D F F
ZP N N N D
FP J J J J
F F D D J J F F K D

样例输出 #1

FP
DEAD
DEAD
J J J J J J D

提示

样例解释

第一回合： 主猪没有目标可以表敌意； 接下来忠猪使用了 $3$ 张南猪入侵，主猪掉了 $3$ 点体力，并认为该角色为类反猪，$3$ 号角色尽管手里有无懈可击，但是因为自己未表明身份，所以同样不能对自己用，乖乖掉 $3$ 点体力；

下一回合： 反猪无牌可出； 接下来主猪对着类反猪爆发，使用 $4$ 张决斗，忠猪死亡，结果主猪弃掉所有牌； * 下来反猪摸到 $1$ 张杀直接杀死主猪获胜。

子任务

一共 $20$ 组测试数据，每个点 $5$ 分。

$10\%$ 的数据没有锦囊牌，另外 $20\%$ 的数据没有无懈可击。

#include<cstdio>
#include<cmath>
int f[50005];
int n;
int text[50005];//每一个点属于哪一个班
int text2[224];//每一个班的开头
int text3[224];
int num[224];//sqrt(50000)+1
void add(int a/*区间开始*/,int b/*区间结束*/,int c/*修改值*/){
    int l,r;//第一个完整修改的班级和最后一个完整修改的班级
    if(a!=text2[text[a]]){//如果区间开始不是那个班级的开头
        l=text2[text[a]+1];
    }
    if(b!=text2[text[b]+1]-1){//如果区间结束不是那个班级的结束
        r=text2[text[b]-1];
    }
    for(int i = l;i <= r;i++){
        num[i]+=c;//大段维护
    }
    if(a!=text2[text[a]])
        for(int i = text2[l]-1;i>=a;i--){
            f[i]+=c;//小段暴力（开头）
        }
    if(b!=text2[text[b]]-1)
        for(int j = text2[r];j <= b;j++){
            f[j]+=c;//小段暴力（结尾）
        }

}
int main(){
    scanf("%d",&n);
    int k = 0;
    for(int i = 0;i <= n;i+=sqrt(n)){
        text2[k]=i;
        if(i!=0){
            text3[k]=i-1;
        }
        for(int j = i;j < i+sqrt(n);j++){
            text[j]=k;
        }
        k++;
    }
    for(int i = 0;i < n;i++){
        scanf("%d",&f[i]);
    }
    int a,b,c,d;
    for(int i= 0 ;i < n;i++){
        scanf("%d%d%d%d",&a,&b,&c,&d);
        if(a==0){
            add(b-1,c-1,d);
        }else{
            printf("%d\n",num[text[c-1]]+f[c-1]);//集体+个人=总共
        }
    }
    return 0;
}

loj6277

@zuotingting@乙鸟

何时月赛？？？

这次请多出点图论！！！

难死那些蒟蒻！！！

最好难度是普及/提高-到提高/省选-

比洛谷月赛简单点。

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
struct node{
    int num;
    int w;
};
vector<node>gv[10005];
int n,m,s;
int dj[10005];
bool inque[10005];
int main(){
    for(int i = 0;i <10005;i++){
        dj[i]=-1;
        inque[i]=true;
    }
    cin>>n>>m>>s;
    for(int i = 0;i < m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        node temp;
        temp.num=b;
        temp.w=c;
        gv[a].push_back(temp);
    }
    dj[s]=0;
    int s = 1;
    for(int i = 0;i < n;i++){
        int mi=s;
        for(int j = 1;j <= n;j++){
            if(dj[j]<dj[mi]&&inque[j]&&dj[j]!=-1){
                mi=j;
            }
        }
        inque[mi]=false;
        int a=1;
        for(int j = 0;j < gv[mi].size();j++){
            if(dj[mi]+gv[mi][j].w<dj[gv[mi][j].num]||dj[gv[mi][j].num]==-1){
                dj[gv[mi][j].num]=dj[mi]+gv[mi][j].w;   
                if(dj[gv[mi][j].num]>dj[a]){
                    a=gv[mi][j].num;
                }
            }
        }
        s=a;
    }
    for(int i = 1;i <= n;i++){
        if(dj[i]==-1)
            cout<<2147483647<<" ";
        else
            cout<<dj[i]<<" ";
    }
    return 0;
}

洛谷3371

我用的是Dijkstra算法（图论）

哪里错了？？

@xushuoxin @昊然 @乙鸟 @zuotingting

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int N,sx,sy,tx,ty;
struct node{
    int x,y,r,fa;
};
node gv[3005];
int find(int x){
    if(gv[x].fa!=x) gv[x].fa=find(gv[x].fa);
    return gv[x].fa;
}
void together(int x,int y){
    int a,b;
    a=find(x);
    b=find(y);
    gv[a].fa=b;
}
int dist(int a,int b,int c,int d){
    return sqrt((a-c)*(a-c)+(b-d)*(b-d));
}
int main(){
    cin>>N;
    cin>>sx>>sy>>tx>>ty;
    for(int i = 0;i < N;i++){
        cin>>gv[i].x>>gv[i].y>>gv[i].r;
        gv[i].fa=i;
    }
    for(int i = 0;i < N;i++){
        for(int j = 0;j < N;j++){
            if(i==j) continue;
            if(dist(gv[i].x,gv[i].y,gv[j].x,gv[j].y)<=gv[i].r+gv[j].r&&dist(gv[i].x,gv[i].y,gv[j].x,gv[j].y)>=abs(gv[i].r-gv[j].r)) together(i,j);
        }
    }
    int a,b;
    for(int i = 0;i < N;i++){
        if(dist(gv[i].x,gv[i].y,sx,sy)==gv[i].r){
            a=i;
            break;
        }
    }
    for(int i = 0;i < N;i++){
        if(dist(gv[i].x,gv[i].y,tx,ty)==gv[i].r){
            b=i;
            break;
        }
    }
    a=find(a);
    b=find(b);
    if(a==b){
        cout<<"Yes";
    }else{
        cout<<"No";
    }
    return 0;
}

atcoder.jp: abc259_d

luogu: AT_abc259_d

此题是图论（并查集）

请看看，不知为何WA。

还有，以下是一个大牛的AcCode：

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

int x[3005],y[3005],r[3005],p[3005];

int find(int x){
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}

int dist(int x1,int y1,int x2,int y2){
   return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}

signed main(){
    int n,sx,sy,tx,ty,ts,ss;
    cin>>n;
    cin>>sx>>sy>>tx>>ty;

    for(int i=1;i<=n;i++){
        cin>>x[i]>>y[i]>>r[i];
        if(dist(sx,sy,x[i],y[i])==r[i]*r[i]) ss=i;
        if(dist(tx,ty,x[i],y[i])==r[i]*r[i]) ts=i;
    }

    for(int i=1;i<=n;i++) p[i]=i;

    for(int i=1;i<=n;i++) 
      for(int j=1;j<=n;j++) 
        if(dist(x[i],y[i],x[j],y[j])<=(r[i]+r[j])*(r[i]+r[j])&&dist(x[i],y[i],x[j],y[j])>=abs(r[i]-r[j])*abs(r[i]-r[j])) 
            p[find(i)]=find(j);

    cout<<(find(ss)==find(ts)?"Yes":"No");
}

www.luogu.com.cn/team/60835

下到语法1

上到算法4

都可以加入！！！

www.luogu.com.cn/contest/113447