Wy Online Judge

WyOJ

降幂定理记录

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-01-03 11:54:23

$a^n\%p=a^{n\%(p-1)}\%p.$

当$p$是素数时成立。

阅读全文

P7078 [CSP-S2020] 贪吃蛇题解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-01-16 20:08:54

难度：$\color{black}\text{NOI/NOI+/CTSC}$

$\color{green}\text{AC算法：}$贪心，队列

题目分析：

题面不用解释,就是让回答有多少蛇将存活。

显然，蛇保命的优先级最高，在自身能保命的前提下尽可能多的弄死别的蛇 ~~（让我想起了海盗分金问题）~~

设当前蛇为 $dq$

可以分两种情况讨论：
1、 $dq$ 吃了最弱的蛇之后不会变成最弱的蛇
2、 $dq$ 吃了最弱的蛇之后会变成最弱的蛇

对于情况一：
显然可以大胆吃

对于情况二：
设 $dq$ 进食后，新的老大为 $dq2$。此时 $dq2$也遇到了相同两种情况。如果 $dq2$ 进食之后不会变成最弱的蛇，那么 $dq2$ 一定会吃掉 $dq$，$dq$ 不应该进食。如果 $dq2$ 进食之后会变成最弱的，那么那就再看 $dq3$ 的情况........就这样递归下去。直到有一条蛇可以吃或者只剩下两条蛇。此时设第 $i$ 个蛇可以放心吃。那么第 $i-1$ 条蛇就不应该吃，否则将在下一轮被吃掉。而第 $i-2$ 条蛇可以吃，因为它知道第 $i-1$ 条蛇不敢吃它。
现在就有了一个结论：对于第 $i$ 轮递归的蛇可以大胆吃，如果 $i$ 为奇数，那么当前蛇就不应该吃；如果 $i$ 为偶数，那么当前蛇就可以大胆吃，然后转化为 $i$ 为奇数的稳定状态。（当然如果只有两条蛇那么只有一条蛇可以存活）

题目分析完毕，剩余的在注释里。

AC代码：

#include <bits\/stdc++.h>
using namespace std;
const int maxn=1e6+5;
#define reg register
int a[maxn];
int t;
int n;
int k;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(int x)
{
    if(x<0)
    {
        putchar('-');
        x=-1;
    }
    if(x>9)write(x\/10);
    putchar(x%10+'0');
}
int main()
{
    t=read();
    int testcnt=0;
    while(t--)
    {
        testcnt++;
        int ans=0;
        if(testcnt==1)
        {
            n=read();
            for(reg int i=1;i<=n;i++)
            {
                a[i]=read();
            }
        }
        if(testcnt>1)
        {
            k=read();
            reg int x,y;
            for(reg int i=1;i<=k;i++)
            {
                x=read();
                y=read();
                a[x]=y;
            }
        }
        deque<pair<int,int> > que1;
        deque<pair<int,int> > que2;
        for(reg int i=1;i<=n;i++)
        {
            que1.emplace_back(make_pair(a[i],i));
        }
        while(1)
        {
            if(que1.size()+que2.size()==2)
            {
                ans=1;
                break;
            }
            \/\/取出最弱
            int y=que1.front().first;
            que1.pop_front();
            \/\/取出最强
            int x;
            int bianhao;\/\/最强者编号
            if(que2.empty()||(!que1.empty()&&que1.back()>que2.back()))
            {\/\/如果que1不空且它的最后一个元素是两个队列最大的才行
            \/\/但是如果que2没有就只能选que1
                x=que1.back().first;
                bianhao=que1.back().second;
                que1.pop_back();
            }
            else{
                x=que2.back().first;
                bianhao=que2.back().second;
                que2.pop_back();
            }
            pair<int,int> xianzai=make_pair(x-y,bianhao);
            if(que1.empty()||xianzai<=que1.front())\/\/pair自动比较第一个参数
            {\/\/最强蛇进食之后变成了最弱蛇
                ans=que1.size()+que2.size()+2;
                \/\/先假设不吃
                int count=0;
                \/\/第几轮递归
                while(1)
                {
                    count++;
                    if(que1.size()+que2.size()+1==2)
                    {
                        if(!(count&1))ans--;
                        \/\/可以发现，当轮数为偶数时，当前最强才能放心吃
                        break;
                    }
                    \/\/重新选择当前最强递归下去
                    if(que2.empty()||!que1.empty()&&que1.back()>que2.back())
                    {   \/\/如果que1不空且它的最后一个元素是两个队列最大的才行
                        \/\/但是如果que2没有就只能选que1
                        x=que1.back().first;
                        bianhao=que1.back().second;
                        que1.pop_back();
                    }
                    else{
                        x=que2.back().first;
                        bianhao=que2.back().second;
                        que2.pop_back();
                    }
                    xianzai=make_pair(x-xianzai.first,bianhao);\/\/之前的最强已经是最弱了，让现在的最强进食
                    if(!((que1.empty()||xianzai<que1.front())&&(que2.empty()||xianzai<que2.front())))
                    {\/\/如果不是最弱的，那么看看能不能吃
                        if(!(count&1))
                        {
                            ans--;
                        }
                        break;
                    }
                }
                break;
            }
            else
            {
                que2.emplace_front(xianzai);
                \/\/如果吃掉后不是最弱，那么大胆吃！
            }
        }
        write(ans);
        putchar('\n');
    }
    return 0;
}

阅读全文

P1526 [NOI2003] 智破连环阵题解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-01-17 21:06:48

难度：$\color{black}\text{NOI/NOI+/CTSC}$

题面：

不需要解释

题目分析：

注意，第 $i$ 号武器被摧毁后第 $i+1$ 号武器就会立即进入攻击状态。炸弹的那个持续引爆5分钟实际上就是说炸弹能摧毁的武器都会立即摧毁，那个5分钟实际上没有用，例如第$1,2,3,4,6$号武器在攻击范围内，那么炸弹将会瞬间摧毁$1,2,3,4$号武器。
可以开个数组 attack[maxn][maxn]，记录第 $j$ 个武器是否在第 $i$ 个炸弹的攻击范围内。这么处理：

for(reg int i=1;i<=n;i++)
{
    for(reg int j=1;j<=m;j++)
    {
        if(k*k>=((zd[i].x-wq[j].x)*(zd[i].x-wq[j].x)+(zd[i].y-wq[j].y)*(zd[i].y-wq[j].y)))\/\/k*k省去开根运算
        {
            attack[i][j]=1;
        }
    }
}

然后跑个dp求解第$i$个武器攻击的情况下从第 $j$ 个武器炸起最大能炸到的武器编号：

for(reg int i=1;i<=n;i++)
{
    for(reg int j=m;j>0;j--)
    {
        if(!attack[i][j])continue;
        max_attack[i][j]=max(j,max_attack[i][j+1]);
    }
}

再跑个dp求解从第 $i$ 个武器炸起炸毁最后一个武器最少需要多少武器

for(reg int i=m;i>0;i--)
{\/\/dp
    for(reg int j=1;j<=n;j++)
    {
        if(!attack[j][i])continue;
        min_zd[i]=min(min_zd[i],min_zd[max_attack[j][i]+1]+1);
    }\/\/当前炸起最远能炸到max_attack[j][i]，加上1就到了下一个炸弹所对应的武器区间。
    \/\/所以min_zd[max_attack[j][i]+1]就是下一个炸弹对应的武器区间炸起所需要的最少炸弹。
    \/\/min_zd[max_attack[j][i]+1]还要加上1是因为要考虑到min_zd[max_attack[j][i]+1]是后面的武器区间，
    \/\/还需要算上当前炸弹。
}

然后定义一个数组wcpd[maxn][maxn]，代表第 $i$ 个武器是否对应第 $j$个武器区间再定义一个数组vis[maxn][maxn]，用于匈牙利算法

然后就是dfs了，定义：

void dfs(int x,int qj);\/\/到了第x个武器，分了qj个区间

然后定义一个数组huisu，用于暂时存储

然后从 $x \rightarrow m$枚举武器($i$)，从 $1 \rightarrow n$ 枚举炸弹($j$)，如果武器 $x$ 在当前炸弹的攻击范围内($attack[j][x]==true$)并且当前炸弹从 $x$ 炸起最大能炸到的编号($max_attack[j][x]$) $\ge$ 当前枚举武器编号($i$) ($max_attack[j][x]$ $\ge$ $i$),那么标记上第 $j$ 个武器对应第 $i$个武器区间（$ wcpd[j][qj+1]=1$）。然后用匈牙利算法看一下当前炸弹是否能匹配上，如果能，那么递归下去即可。最后要注意回溯。这一部分的代码：

bool xylsf(int x)\/\/匈牙利算法
{
    for(int i=1;i<=n;i++)
    {
        if(wcpd[i][x]&&!vis[i])
        {
            vis[i]=1;
            if(!dy[i]||xylsf(dy[i]))
            {
                dy[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
void dfs(int x,int qj)\/\/到了第x个武器，分了qj个区间
{
    if(qj+min_zd[x]>=ans)return;\/\/剪枝
    if(x>m)
    {
        ans=qj;
        return;
    }
    int huisu[maxn];\/\/用于回溯
    for(reg int i=x;i<=m;i++)
    {
        for(reg int j=1;j<=n;j++)
        {
            huisu[j]=dy[j];
            if(attack[j][x]&&max_attack[j][x]>=i)
            {
                wcpd[j][qj+1]=1;\/\/j控制了qj++的武器区间
            }
        }
        memset(vis,0,sizeof(vis));
        if(xylsf(qj+1))dfs(i+1,qj+1);
        \/\/接下来是回溯
        for(reg int j=1;j<=n;j++)
        {
            dy[j]=huisu[j];
            if(attack[j][x]&&max_attack[j][x]>=i)
            {
                wcpd[j][qj+1]=0;\/\/j控制了qj++的武器区间
            }
        }
    }
}

题目分析完毕

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
#define reg register
int n,m,k;
const int maxn=105;
bool attack[maxn][maxn];\/\/第i个炸弹是否能炸掉第j个武器
int max_attack[maxn][maxn];\/\/第i个炸弹进行攻击，从第j个武器开始炸能攻击到的最大编号武器
int min_zd[maxn];\/\/从第i个开始炸起，最少要用多少炸弹才能炸掉最后的武器
int ans;
int dy[maxn];\/\/一个炸弹配对了那些
bool wcpd[maxn][maxn];
bool vis[maxn];
struct Wq\/\/武器
{
    int x,y;
}wq[maxn];
struct Zd\/\/炸弹
{
    int x,y;
}zd[maxn];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
bool xylsf(int x)\/\/匈牙利算法
{
    for(int i=1;i<=n;i++)
    {
        if(wcpd[i][x]&&!vis[i])
        {
            vis[i]=1;
            if(!dy[i]||xylsf(dy[i]))
            {
                dy[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
void dfs(int x,int qj)\/\/到了第x个武器，分了qj个区间
{
    if(qj+min_zd[x]>=ans)return;\/\/剪枝
    if(x>m)
    {
        ans=qj;
        return;
    }
    int huisu[maxn];\/\/用于回溯
    for(reg int i=x;i<=m;i++)
    {
        for(reg int j=1;j<=n;j++)
        {
            huisu[j]=dy[j];
            if(attack[j][x]&&max_attack[j][x]>=i)
            {
                wcpd[j][qj+1]=1;\/\/j控制了qj++的武器区间
            }
        }
        memset(vis,0,sizeof(vis));
        if(xylsf(qj+1))dfs(i+1,qj+1);
        \/\/接下来是回溯
        for(reg int j=1;j<=n;j++)
        {
            dy[j]=huisu[j];
            if(attack[j][x]&&max_attack[j][x]>=i)
            {
                wcpd[j][qj+1]=0;\/\/j控制了qj++的武器区间
            }
        }
    }
}
inline void indata()
{
    m=read();
    n=read();
    k=read();
    for(reg int i=1;i<=m;i++)
    {
        wq[i].x=read();
        wq[i].y=read();
    }
    for(reg int i=1;i<=n;i++)
    {
        zd[i].x=read();
        zd[i].y=read();
    }
}
inline void init()
{
    for(reg int i=1;i<=n;i++)
    {
        for(reg int j=1;j<=m;j++)
        {
            if(k*k>=((zd[i].x-wq[j].x)*(zd[i].x-wq[j].x)+(zd[i].y-wq[j].y)*(zd[i].y-wq[j].y)))\/\/k*k省去开根运算
            {
                attack[i][j]=1;
            }
        }
    }
    for(reg int i=1;i<=n;i++)
    {
        for(reg int j=m;j>0;j--)
        {
            if(!attack[i][j])continue;
            max_attack[i][j]=max(j,max_attack[i][j+1]);
        }
    }
    for(reg int i=1;i<=m;i++)min_zd[i]=0x3f3f3f3f;
    for(reg int i=m;i>0;i--)
    {\/\/dp
        for(reg int j=1;j<=n;j++)
        {
            if(!attack[j][i])continue;
            min_zd[i]=min(min_zd[i],min_zd[max_attack[j][i]+1]+1);
        }\/\/当前炸起最远能炸到max_attack[j][i]，加上1就到了下一个炸弹所对应的武器区间。
        \/\/所以min_zd[max_attack[j][i]+1]就是下一个炸弹对应的武器区间炸起所需要的最少炸弹。
        \/\/min_zd[max_attack[j][i]+1]还要加上1是因为要考虑到min_zd[max_attack[j][i]+1]是后面的武器区间，
        \/\/还需要算上当前炸弹。
    }
    ans=n;
}
int main()
{
    indata();
    init();
    dfs(1,0);
    printf("%d",ans);
    return 0;
}

阅读全文

P1082 [NOIP2012 提高组] 同余方程题解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-01-19 10:41:29

置顶消息：

zgc大佬认为本题解的 $x = (x \mod b + b) \mod b$ 是错的，看来本题解应该是出错了，但是我太弱了不会改，这篇题解很垃圾

难度：$\color{green}\text{普及+/提高}$

题目分析：

题目要求关于 $x$ 的方程 $ax \equiv 1(\mod b)$ ，也就是 $ax \mod b = 1$ 的最小整数解。
可以发现，$x$ 就是 $a$的逆元，记作 $inv(a)$，然后方程转换为：
$a \times inv(a) + b \times y = 1$
这么转化的原因是 $a \times inv(a)$ 与 $1$ 之间的差肯定是 $b$ 的倍数。（$y$ 代表 $b$ 的多少倍，可以为负数）
转化完之后就可以直接用扩欧求解了。
最后答案可能不是最小，也可能是负数。
先上一个式子:
若 $ax \mod b = 1$,
那么 $a(x+bn) \mod b = 1$
$n$ 是一个变量。
所以最后如果 $x$ 是负数，就大量加上 $b$ 变为正数，如果太大就大量减去 $b$ 即可。
最后处理的式子： $x = (x \mod b + b) \mod b$
注解：$x \mod b + b$处理负数，最后括号外面的 $\mod b$ 处理正数。

代码：

#include <bits\/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b;
ll x,y;
void exgcd(ll a,ll b)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b);
    ll tmp=x;
    x=y;
    y=tmp-a\/b*y;
}
int main()
{
    scanf("%lld%lld",&a,&b);
    exgcd(a,b);
    printf("%lld",(x%b+b)%b);
    return 0;
}

阅读全文

P1516 青蛙的约会推式子过程

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-01-20 16:15:41

懒得写题解，就把推算过程放上来

$x+mt \equiv y+nt (\mod L)$
因此
$(x+mt)-(y+nt)$ 一定为 $L$ 的倍数
$(x+mt)-(y+nt) = aL$
$(x+mt)-(y+nt)-aL = 0$
$(x-y)+t(m-n)-aL=0$
$t(n-m)+aL=(x-y)$
设 $w = n-m$，$b = x-y$。
$ tw + aL=b$
$w,L,b$ 为常数
设 $c = GCD(w,L)$
若 $b \mod c \neq 0$，无解。
对这个方程：$tw+aL = c$ 求一组解 $t0,a0$
然后两边同时乘$(b/c)$ 变为：
$t0 \cdot w \cdot (b/c) + a0 \cdot L \cdot (b/c) = d$
因为要求的是 $t$，那么本题的解就是：
$t0 * (b/c)$
然后因为要求最小解，那么处理一下：
$ans = (t0 *(b/c) \mod (L \div c) + (L \div c)) \mod (L \div c)$

阅读全文

中国剩余定理(crt)学习记录

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-01-20 16:50:36

对于这样一个方程组：
$\begin{cases} x \equiv a1 (\mod mod1)\ x \equiv a2 (\mod mod2)\\
x \equiv a3 (\mod mod3)\ \cdots\cdots\ x \equiv an (\mod modn) \end{cases}$
设一个数 $MUL = \Pi_{i=1}^{n} modi$
设 $MODi = \frac{a}{modi}$
设 $Ci$ 为 $MODi$ 在模 $modi$ 意义下的逆元
解： $x = \Sigma_{i=1}^{n} ai \cdot MODi \cdot Ci$
注解：因为 $Ci$ 为 $MODi$ 的逆元，$MODi \cdot Ci \equiv 1 (\mod modi)$，乘上$ai$，就变为 $ai \cdot MODi \cdot Ci \equiv ai (\mod modi)$ 了
最后 $ans = x \mod MUL $

阅读全文

P2158 [SDOI2008] 仪仗队题解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-01-21 11:28:49

难度：$\color{blue}\text{提高+/省选-}$

前言：

~~这题是蓝题但是很水~~

题目分析：

~~瞄一眼就能发现~~这个方阵可以被左下---右上对角线分成对称的两部分（中间的对角线是单独的一部分，单独计算）。就只看下面那半部分好了，可以发现，对于第 $i$ 列（$i \ge 2$，从左数），能看到的人数就是 $\phi(i-1)$。所以这半部分总共能看到的人数就是 $\Sigma_{i=2}^{n}\phi(i-1)$。
另一部分和这一部分的答案一样。至于剩下的那个对角线，可以发现对角线上肯定只有第一个人能被看见。
所以上下两部分加上对角线总共能看到的人数就是：
$2\cdot \Sigma_{i=2}^{n}\phi(i-1)+1$
复杂度：$\Theta(n\sqrt{n})$

特殊情况：

如果 $n = 1$，那么答案应该为 $0$，要特判一下。

欧拉函数：

设一个数为 $x$，欧拉函数就是求有多少个数 $i$ $(1 \le i \le x)$，与 $x$ 互质 $(gcd(i,x)=1)$ 。记作 $\phi(x)$。
放上个求 $\phi(x)$ 的板子：

int eular(int n)
{
    int ret=1;
    for(reg int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            n\/=i;
            ret*=(i-1);
            while(n%i==0)
            {
                n\/=i;
                ret*=i;
            }
        }
    }
    if(n>1)ret*=n-1;
    return ret;
}

$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
#define reg register
int n;
int eular(int n)
{
    int ret=1;
    for(reg int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            n\/=i;
            ret*=(i-1);
            while(n%i==0)
            {
                n\/=i;
                ret*=i;
            }
        }
    }
    if(n>1)ret*=n-1;
    return ret;
}
signed main()
{
    scanf("%lld",&n);
    if(n==1)
    {
        printf("0");
        return 0;
    }
    int ans=0;
    for(reg int i=2;i<=n;i++)
    {
        ans+=eular(i-1);
    }
    ans=(ans<<1)+1;
    if(ans<0)return -1;
    printf("%d",ans);
    return 0;
}

阅读全文

CF1633B Minority题解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-02-02 21:06:29

题目大意：

给定一个数组。可以随便选一个子区间执行这样的操作：
一、如果这个子区间 $0$ 和 $1$ 的数量相同，不执行操作
二、如果这个子区间 $0$ 和 $1$ 的数量不同，若 $0$ 的数量严格小于 $1$ ，那么删除子区间所有的 $0$ ，反之删除子区间所有的 $1$ 。
求最多能删除的元素个数

题目解法：

第一眼看到，只能想到 $O(n^2)$的暴力（我太菜了）
再想想，可以发现可以贪心的选择整个数组执行操作。这样就能保证删除元素最多了。
如果 $0$ 和 $1$ 数量相等呢？只需要从区间头部或尾部随便删去一个元素就行了。

AC代码：

#include <bits\/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int t;
int n;
const int maxn=2e5+5;
char a[maxn];
int zero;
int one;
int ans;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        zero=one=0;
        scanf("%s",a+1);
        n=strlen(a+1);
        for(int i=1;i<=n;i++)
        {
            if(a[i]=='0')zero++;
            if(a[i]=='1')one++;
        }
        ans=min(zero,one);
        if(zero==one)ans--;
        printf("%d\n",ans);
    }
 \/\/   system("pause");
    return 0;
}

阅读全文

CF1633C题解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-02-04 20:10:22

题目意思：

一个角色与怪物决斗。
角色有以下两个属性：
1.$hc$：生命值
2.$dc$：攻击力
怪物有以下两个属性：
1.$hm$：生命值
2.$dm$：攻击力

决斗方式：
1.角色向怪物发动攻击，怪物生命值掉了 $dc$。
2.怪物向角色发动攻击，角色生命值掉了 $dm$。
如此循环，直到其中一方的生命值小于等于 $0$，另一方获胜。

决斗开始之前，角色可以购买装备，角色有 $k$ 枚硬币，一个硬币可以使生命值增加 $a$，也可以使攻击力增加 $w$。
求如果以最优的方式购买装备，角色是否能打败怪物。

有 $t$ 组数据，$1 \le t \le 5 \cdot 10^4$。

题目分析：

看到这道题，可以发现测试数据组数很多，可能需要 $O(1)$ 回答每组询问，但是，既然是要求最优方案，难以做到 $O(1)$ 回答询问。
此时可以发现，题目里面说了，所有测试数据的 $k$ 之和不超过 $2 \cdot 10^5$。所以直接枚举分配给生命值和角色的硬币数量，对于枚举到的每组方案显然可以 $O(1)$ 判断角色是否可以胜利，如果可以胜利输出 YES，如果所有方案都不可行输出 NO。~~（我到比赛结束前十几分钟才发现这个最后没时间写了）~~ 这道题就做出来了。

注意事项：

如果就这样写，将会在第 $13$ 个测试点 WA 掉，原因是神仙 hacker 造的数据会爆掉 long long，所以在 C++20 下开 __int128 即可。

AC代码：

#include <bits\/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int t;
signed main()
{
    scanf("%lld",&t);
    int hc,dc,hm,dm,k,w,a;
    while(t--)
    {
        scanf("%lld%lld",&hc,&dc);\/\/角色的生命和攻击力
        scanf("%lld%lld",&hm,&dm);\/\/怪物的生命和攻击力
        scanf("%lld%lld%lld",&k,&w,&a);
        bool flag=0;
        for(int i=0;i<=k;i++)
        {
            int gjl=(k-i)*w+dc;\/\/新的攻击力
            int sd=hm\/gjl-1;\/\/杀死怪物时受到伤害的次数
            if(hm%gjl>0)sd++;
            if((__int128)hc+(__int128)i*(__int128)a>(__int128)sd*(__int128)dm)
            {
                printf("YES\n");
                flag=1;
                break;
            }
        }
        if(!flag)printf("NO\n");
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}

阅读全文

How to AK Educational Codeforces Round 122 (1633)

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-02-06 20:00:52

A题 Div. 7

签到题，$\color{green}\text{AC代码：}$

#include <bits\/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int t;
int n;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        if(n%7==0)
        {
            cout<<n<<endl;
            continue;
        }
        int zh=n%10;\/\/最后一位
        int m=n%7;
        if(zh-m>=0)
        {
            cout<<n-m<<endl;
            continue;
        }
        if(zh-m<0)
        {
            cout<<n-m+7<<endl;
        }
    }
 \/\/   system("pause");
    return 0;
}

B题 Minority

题目大意：

题目解法：

AC代码：

#include <bits\/stdc++.h>
using namespace std;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int t;
int n;
const int maxn=2e5+5;
char a[maxn];
int zero;
int one;
int ans;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        zero=one=0;
        scanf("%s",a+1);
        n=strlen(a+1);
        for(int i=1;i<=n;i++)
        {
            if(a[i]=='0')zero++;
            if(a[i]=='1')one++;
        }
        ans=min(zero,one);
        if(zero==one)ans--;
        printf("%d\n",ans);
    }
 \/\/   system("pause");
    return 0;
}

C题 Kill the Monster

题目意思：

一个角色与怪物决斗。
角色有以下两个属性：
1.$hc$：生命值
2.$dc$：攻击力
怪物有以下两个属性：
1.$hm$：生命值
2.$dm$：攻击力

有 $t$ 组数据，$1 \le t \le 5 \cdot 10^4$。

题目分析：

注意事项：

如果就这样写，将会在第 $13$ 个测试点 WA 掉，原因是神仙 hacker 造的数据会爆掉 long long，所以在 C++20 下开 __int128 即可。

AC代码：

#include <bits\/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int t;
signed main()
{
    scanf("%lld",&t);
    int hc,dc,hm,dm,k,w,a;
    while(t--)
    {
        scanf("%lld%lld",&hc,&dc);\/\/角色的生命和攻击力
        scanf("%lld%lld",&hm,&dm);\/\/怪物的生命和攻击力
        scanf("%lld%lld%lld",&k,&w,&a);
        bool flag=0;
        for(int i=0;i<=k;i++)
        {
            int gjl=(k-i)*w+dc;\/\/新的攻击力
            int sd=hm\/gjl-1;\/\/杀死怪物时受到伤害的次数
            if(hm%gjl>0)sd++;
            if((__int128)hc+(__int128)i*(__int128)a>(__int128)sd*(__int128)dm)
            {
                printf("YES\n");
                flag=1;
                break;
            }
        }
        if(!flag)printf("NO\n");
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}

D题 Make Them Equal

题目意思：

有 $3$ 个大小为 $n$ 的数组，$a$，$b$ 和 $c$
给定 $a$ 和 $b$。$a$ 数组初始所有值都为 $0$。

有 $k$ 次操作，每次操作可以过程如下：

选择两个整数 $i$ 和 $x$ $(1 \le i \le n,x \ge 1)$
$a_i$ 变为 $a_i + \frac{a_i}{x}$

若 $a_i = b_i $，则获得 $c_i$ 的分数。
求经过 $k$ 此操作最多能获得的分数。

数据范围：

有 $t$ 组数据 $(1 \le t \le 100)$。
$1 \le n \le 10^3$。
$1 \le b_i \le 10^3$。
$1 \le c_i \le 10^6$。

题目分析：

定义一个数组 $dis$，$dis_i$ 代表$1 \rightarrow i$，最小转换次数，由于 $n$ 特别小，可以 $O(n^2)$ 预处理。
定义一个数组 $f$ ，$f_i$ 代表操作次数为 $i$ 时最多能获得多少分。
可以发现 $1$ 到 $10^3$ 次方的范围内，最多转换 $12$ 次。总共操作数就是 $min(12 \cdot n,k)$。超过了 $12 \cdot n$ 就无意义了。
对于每组询问跑 dp 处理 $f$ 数组。
设 $p = min(12 \cdot n,k)$
最终答案就是 $f_p$。

AC代码：

#include <bits\/stdc++.h>
using namespace std;
const int maxn=1e3+5;
int t;
int n,k;
int b[maxn];
int c[maxn];
int dis[maxn];\/\/从1到i最少多少步
int f[maxn*12];\/\/操作数量为i时最大收益
int main()
{
    memset(dis,0x3f3f3f3f,sizeof(dis));
    dis[1]=0;
    for(int i=1;i<=maxn;i++)
    {
        for(int j=1;j<=i;j++)
        {
            dis[i+i\/j]=min(dis[i+i\/j],dis[i]+1);
        }
    }
    scanf("%d",&t);
    while(t--)
    {
        memset(f,0,sizeof(f));
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&c[i]);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=min(k,12*n);j>=dis[b[i]];j--)
            {
                f[j]=max(f[j],f[j-dis[b[i]]]+c[i]);
            }
        }
        printf("%d\n",f[min(k,12*n)]);
    }
    #ifndef ONLINE_JUDGE
    system("pause");
    #endif
    return 0;
}

阅读全文

Wy Online Judge

WyOJ

降幂定理记录

P7078 [CSP-S2020] 贪吃蛇 题解

难度：$\color{black}\text{NOI/NOI+/CTSC}$

$\color{green}\text{AC算法：}$贪心，队列

题目分析：

AC代码：

P1526 [NOI2003] 智破连环阵题解

难度：$\color{black}\text{NOI/NOI+/CTSC}$

题面：

题目分析：

$\color{green}\text{AC代码：}$

P1082 [NOIP2012 提高组] 同余方程题解

置顶消息：

难度：$\color{green}\text{普及+/提高}$

题目分析：

代码：

P1516 青蛙的约会 推式子过程

懒得写题解，就把推算过程放上来

中国剩余定理(crt)学习记录

P2158 [SDOI2008] 仪仗队题解

难度：$\color{blue}\text{提高+/省选-}$

前言：

题目分析：

特殊情况：

欧拉函数：

$\color{green}\text{AC代码：}$

CF1633B Minority题解

题目大意：

题目解法：

AC代码：

CF1633C题解

题目意思：

题目分析：

注意事项：

AC代码：

How to AK Educational Codeforces Round 122 (1633)

A题 Div. 7

B题 Minority

题目大意：

题目解法：

AC代码：

C题 Kill the Monster

题目意思：

题目分析：

注意事项：

AC代码：

D题 Make Them Equal

题目意思：

数据范围：

题目分析：

AC代码：

P7078 [CSP-S2020] 贪吃蛇题解

P1516 青蛙的约会推式子过程