头像

北海没有WA

$\Huge\color{#FFD4A9}{青涩の醉挽清风}$




离线:7小时前


最近来访(1338)
用户头像
yxc的小迷妹
用户头像
闻天语
用户头像
acwing_064
用户头像
宇宙有边
用户头像
DreamFather
用户头像
szliangbr
用户头像
incra
用户头像
洛白さん
用户头像
北海只有WA
用户头像
_memory_
用户头像
Finn2009
用户头像
亚历山大
用户头像
bcwing
用户头像
吴梦涵2022
用户头像
Destiny688
用户头像
梦若浮生
用户头像
垫底抽風
用户头像
L-China
用户头像
Zzay
用户头像
小小_88

新鲜事 原文

《此处无字胜有字》
图片



会议

题目描述

有一个村庄居住着 $n$ 个村民,有 $n-1$ 条路径使得这 $n$ 个村民的家联通,每条路径的长度都为 $1$。现在村长希望在某个村民家中召开一场会议,村长希望所有村民到会议地点的距离之和最小,那么村长应该要把会议地点设置在哪个村民的家中,并且这个距离总和最小是多少?若有多个节点都满足条件,则选择节点编号最小的那个点。

输入格式

第一行,一个数 $n$,表示有 $n$ 个村民。

接下来 $n-1$ 行,每行两个数字 $a$ 和 $b$,表示村民 $a$ 的家和村民 $b$ 的家之间存在一条路径。

输出格式

一行输出两个数字 $x$ 和 $y$。

$x$ 表示村长将会在哪个村民家中举办会议。

$y$ 表示距离之和的最小值。

样例 #1

样例输入 #1

4
1 2 
2 3 
3 4

样例输出 #1

2 4

提示

数据范围

对于 $70\%$ 数据 $n \le 10^3$。

对于 $100\%$ 数据 $n \le 5 \times 10^4$。


图论升级版~

c31237f70950cdbe2701e12ca32ef8a1.gif

#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 50001
using namespace std;
int deep[maxn],tot,n,ans,head[maxn],s[maxn],size=(1<<30);
bool vis[maxn];
struct node
{
    int to,next;
}a[maxn*2];
void add(int x,int y)
{
    tot++;
    a[tot].to=y;
    a[tot].next=head[x];
    head[x]=tot;
}
void dfs(int x)
{
    vis[x]=1;
    s[x]=0;
    int tmp=0;
    for(int i=head[x];i;i=a[i].next)
    {
        int y=a[i].to;
        if(!vis[y])
        {
            dfs(y);
            s[x]+=s[y]+1;
            tmp=max(tmp,s[y]+1);
        }
    }
    tmp=max(tmp,n-s[x]-1);
    if(tmp<size||tmp==size&&x<ans)
    {
        ans=x;
        size=tmp;
    }
}
void dfs1(int x,int y,int d)
{
    deep[x]=d;
    for(int i=head[x];i;i=a[i].next)
      if(y!=a[i].to)
        dfs1(a[i].to,x,d+1);
}
int main()
{
    int i,j,x,y;
    scanf("%d",&n);
    for(i=1;i<n;i++)
      scanf("%d%d",&x,&y),add(x,y),add(y,x);
    dfs(1);
    dfs1(ans,ans,0);
    int sum=0;
    for(i=1;i<=n;i++)
      sum=sum+abs(deep[i]-deep[ans]);
    printf("%d %d",ans,sum);
    return 0;
}

完结磕头…^2




杂务

题目描述

John的农场在给奶牛挤奶前有很多杂务要完成,每一项杂务都需要一定的时间来完成它。比如:他们要将奶牛集合起来,将他们赶进牛棚,为奶牛清洗乳房以及一些其它工作。尽早将所有杂务完成是必要的,因为这样才有更多时间挤出更多的牛奶。当然,有些杂务必须在另一些杂务完成的情况下才能进行。比如:只有将奶牛赶进牛棚才能开始为它清洗乳房,还有在未给奶牛清洗乳房之前不能挤奶。我们把这些工作称为完成本项工作的准备工作。至少有一项杂务不要求有准备工作,这个可以最早着手完成的工作,标记为杂务$1$。John有需要完成的$n$个杂务的清单,并且这份清单是有一定顺序的,杂务$k(k>1)$的准备工作只可能在杂务$1$至$k-1$中。

写一个程序从$1$到$n$读入每个杂务的工作说明。计算出所有杂务都被完成的最短时间。当然互相没有关系的杂务可以同时工作,并且,你可以假定John的农场有足够多的工人来同时完成任意多项任务。

输入格式

第1行:一个整数$n$,必须完成的杂务的数目($3 \le n \le 10,000$);

第$2$至$(n+1)$行: 共有$n$行,每行有一些用$1$个空格隔开的整数,分别表示:

* 工作序号($1$至$n$,在输入文件中是有序的);

* 完成工作所需要的时间$len(1 \le len \le 100)$;

* 一些必须完成的准备工作,总数不超过$100$个,由一个数字$0$结束。有些杂务没有需要准备的工作只描述一个单独的$0$,整个输入文件中不会出现多余的空格。

输出格式

一个整数,表示完成所有杂务所需的最短时间。

样例 #1

样例输入 #1

7
1 5 0
2 2 1 0
3 3 2 0
4 6 1 0
5 1 2 4 0
6 8 2 4 0
7 4 3 5 6 0

样例输出 #1

23

简单图论:)
!0.gif](https://cdn.acwing.com/media/article/image/2022/12/03/193181_be31d72873-0.gif)

#include<iostream>
using namespace std;
int n;
struct node{
    int time;   
    //完成该项杂物的时间 及 完成该将杂务所需的时间
    int condition;  
    //限制条件:准备时间最长杂务
}Node[10010];
int f(void){
    int an=0; 

    cin>>n;
    Node[0].time=0;
    Node[0].condition=0;
    for(int i=1 i<=n; i++){

        int num;
        cin>>num>>Node[i].time;
        int most_time=0;
        Node[i].condition=0
        while(1)
        {
            cin>>num;
            if(num==0){
                break;
            }

            //最大序号的不一定是最多,找出花费最多时间的杂务 
            if(most_time<Node[num].time){
                most_time=Node[num].time;
                Node[i].condition=num;
            }
        }
        int most_quick = Node[Node[i].condition].time;
        most_quick += Node[i].time;
        Node[i].time = most_quick;
        ans = max(ans, Node[i].time);
    }
    return ans;
}
int main(){
    cout<<f();
    return 0;
} 

完结磕头

bdb31b0c84464f3491fb2983d7d20d3f.gif





CODE(C++)

#include<iostream>
using namespace std;
int main(){
    long long n,i,j,k,s=1,m;
    cin>>m>>n;
    for(i=1;i<=n+m;i++)
    s*=i;
    cout<<s;
} 



约瑟夫问题

题目描述

$n$ 个人围成一圈,从第一个人开始报数,数到 $m$ 的人出列,再由下一个人重新从 $1$ 开始报数,数到 $m$ 的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。

注意:本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 $n-1$ 名小朋友,而该题是全部出圈。

输入格式

输入两个整数 $n,m$。

输出格式

输出一行 $n$ 个整数,按顺序输出每个出圈人的编号。

样例 #1

样例输入 #1

10 3

样例输出 #1

3 6 9 2 7 1 8 5 10 4

提示

$1 \le m, n \le 100$


树状数组?

模拟?

队列?

0 (2).gif.gif)
CODE(C++)

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

queue<int> q;
int n,m;

int main(){
    scanf("%d%d",&n,&m);

    for(int i=1;i<=n;i++){
        q.push(i);
    }
    int cnt=0;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        cnt++;
        if(cnt==m){
            printf("%d ",x);
            cnt=0;continue;
        }
        else{
            q.push(x);
        }
    }
    return 0;
} 

#某谷日常打卡




197038_1aa6f63453-搜狗截图20221024205452.png
$$\large\mathrm{青涩の醉挽清风Team成立于 2022 / 10 / 24 程序员节,目前成员共 12 名}$$

$$\large\mathrm{青涩の醉挽清风Team开始招募啦~}$$
$$\Huge\mathrm{在下面评论区留言加入!!!}$$


$\large\color{eee}{团队主旨与意义}$
$青涩の醉挽清风Team成立于 2022年10月24日程序员节$
$具有象征意义,建立时间凸显出我们对编程,对计算机课程的重视和喜爱$
$我们注重对学术方面的培养,同时也劳逸结合,成员秉持着互帮互助的理念,努力让所有同学都能 实现梦想! $
$我们相信,唯有努力,才能获得成功。千难万难,我们都会集大众之智,攻坚克难$
$我们同时也有着明确的纪律和顽强的团队精神$


$\large\mathrm{青涩の醉挽清风Team进队要求}$

  1. $不抄任何题解$
  2. $洛谷估值 ≥ 100$
  3. $发过题解、学术分享(≥ 3篇),若发的全部都是新鲜事不会同意进$
  4. $周赛进过前 500$
    $满足 1 个即可$
    $若没有满足以上要求但是实在想加,AC Chat私聊团主或我$

# 职务申请要求:

1.具有能严格要求自己的能力
2.具有团队精神和带头作用
3.Saber前100
4.获得周赛勋章


$成员规则:$

  1. $初始分 50,扣光直接踢掉$
  2. $发过(进入团队之后发的)有意义题解或学术分享,一次加 5 分$
  3. $刷屏 1 次扣 2^1 ,2 次扣 2^2 ,3 次扣 2^3,以此类推$
  4. $直接发脏话(缩写可以),扣分同刷屏$
  5. $举报 1 次加 2 分$
  6. $周赛进一次 500,加 20 分$
  7. $爆别人名字一次扣 50 分$
  8. $学术群禁止聊天,扣分规则参考刷屏的$
  9. $未经群主许可,擅自登录群主的号且在群里发消息,踢人等,一经查明,直接关进小黑屋$
  10. $周赛时在群里讨论题目,公布答案等,直接扣成0分;如果导致连坐,群被查封等重大损失,直接送进小黑屋$
  11. $回答有意义的问题,一次加10分$
  12. $第一次犯错不扣分,警告一次$
  13. $改名字要私信告诉我$
  14. $一人最多两个职位$

$团主、副团主、管理员、宣传 and 设计部、大佬、吉祥物规则:$

  1. $初始分 10,扣光降为成员$
  2. $扣的分为普通成员的两倍$
  3. $加的分为普通成员的 1/2$

$黑名单:$

> 1. $被踢出后会把截图和名字挂在这个帖子最底下的小黑屋里$

更详细的团规!


@落月成孤倚灬


$\mathrm{青涩の醉挽清风Team副团长:}$

@闻天语

@Finn2009

@incra


$\mathrm{青涩の醉挽清风Team吉祥物:}$

@重生之我是菜鸟


$\mathrm{青涩の醉挽清风Team管理员:}$

@Finn2009

@09.K

@回归.AC_Boy


$\mathrm{青涩の醉挽清风Team宣传 and 设计部}$

@北海没有WA


$\mathrm{青涩の醉挽清风Team大佬:}$

@incra

@落月成孤倚灬


$\mathrm{青涩の醉挽清风Team成员:}$

@99的手速加上1的运气

@种花家的市长

@种花家的虎式坦克

@kkksc007

@yxc的小迷妹


具体加分规则请咨询@Finn2009


团徽:

197038_3e9c28816e-青涩.png

再强调一遍:

有意愿加入的在帖子底部评论

bdb31b0c84464f3491fb2983d7d20d3f.gif




[SHOI2002] 滑雪

题目描述

Michael 喜欢滑雪。这并不奇怪,因为滑雪的确很刺激。可是为了获得速度,滑的区域必须向下倾斜,而且当你滑到坡底,你不得不再次走上坡或者等待升降机来载你。Michael 想知道在一个区域中最长的滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子:

1   2   3   4   5
16  17  18  19  6
15  24  25  20  7
14  23  22  21  8
13  12  11  10  9

一个人可以从某个点滑向上下左右相邻四个点之一,当且仅当高度会减小。在上面的例子中,一条可行的滑坡为 $24$-$17$-$16$-$1$(从 $24$ 开始,在 $1$ 结束)。当然 $25$-$24$-$23$-$\ldots$-$3$-$2$-$1$ 更长。事实上,这是最长的一条。

输入格式

输入的第一行为表示区域的二维数组的行数 $R$ 和列数 $C$。下面是 $R$ 行,每行有 $C$ 个数,代表高度(两个数字之间用 $1$ 个空格间隔)。

输出格式

输出区域中最长滑坡的长度。

样例 #1

样例输入 #1

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

样例输出 #1

25

提示

对于 $100\%$ 的数据,$1\leq R,C\leq 100$。


题解这东西

水一水就过去了

src=http___c-ssl.duitang.com_uploads_item_201710_03_20171003000500_BYjzV.thumb.400_0.gif&refer=http___c-ssl.duitang.gif
CODE(C++)

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int n,m,a[201][201],s[201][201],ans;
bool use[201][201];
int dfs(int x,int y){
    if(s[x][y])return s[x][y];
    s[x][y]=1;
    for(int i=0;i<4;i++)
    {  int xx=dx[i]+x;
       int yy=dy[i]+y;
       if(xx>0&&yy>0&&xx<=n&&yy<=m&&a[x][y]>a[xx][yy]){
          dfs(xx,yy);
          s[x][y]=max(s[x][y],s[xx][yy]+1);
       }
    }
    return s[x][y];
}
int main()
{   
   scanf("%d%d",&n,&m);
   for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
       scanf("%d",&a[i][j]);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
        ans=max(ans,dfs(i,j));
    printf("%d",ans);
    return 0;
}



后缀表达式

题目描述

所谓后缀表达式是指这样的一个表达式:式中不再引用括号,运算符号放在两个运算对象之后,所有计算按运算符号出现的顺序,严格地由左而右新进行(不用考虑运算符的优先级)。

如:$\texttt{3(5-2)+7}$ 对应的后缀表达式为:$\texttt{3.5.2.-7.+@}$。在该式中,@ 为表达式的结束符号。. 为操作数的结束符号。

输入格式

输入一行一个字符串 $s$,表示后缀表达式。

输出格式

输出一个整数,表示表达式的值。

样例 #1

样例输入 #1

3.5.2.-*7.+@

样例输出 #1

16

提示

数据保证,$1 \leq |s| \leq 50$,答案和计算过程中的每一个值的绝对值不超过 $10^9$。


简单栈就可以解决

微信图片_20221104215128.jpg
CODE(C++)

#include<iostream>
using namespace std;
int main()
{
    char t;
    stack<int> s;
    int num =0 ;
    while(cin>>t&&t!='@')
    {
        if(t == '.') {
            s.push(num);
            num = 0;
        }
        if(t >= '0' && t <= '9') {
            num = num * 10 + t - '0';
        }
        if(t=='+')
        {
            int a=s.top();
            s.pop();
            int b=s.top();
            s.pop();
            s.push(b+a);
        }
        if(t=='-')
        {
            int a=s.top();
            s.pop();
            int b=s.top();
            s.pop();
            s.push(b-a);
        }
        if(t=='/')
        {
            int a=s.top();
            s.pop();
            int b=s.top();
            s.pop();
            s.push(b/a);
        }
        if(t=='*')
        {
            int a=s.top();
            s.pop();
            int b=s.top();
            s.pop();
            s.push(b*a);
        }
    }
    cout<<s.top()<<endl;
    return 0;
} 



小A点菜

题目背景

uim 神犇拿到了 uoi 的 ra(镭牌)后,立刻拉着基友小 A 到了一家……餐馆,很低端的那种。

uim 指着墙上的价目表(太低级了没有菜单),说:“随便点”。

题目描述

不过 uim 由于买了一些书,口袋里只剩 $M$ 元 $(M \le 10000)$。

餐馆虽低端,但是菜品种类不少,有 $N$ 种 $(N \le 100)$,第 $i$ 种卖 $a_i$ 元 $(a_i \le 1000)$。由于是很低端的餐馆,所以每种菜只有一份。

小 A 奉行“不把钱吃光不罢休”,所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。

由于小 A 肚子太饿,所以最多只能等待 $1$ 秒。

输入格式

第一行是两个数字,表示 $N$ 和 $M$。

第二行起 $N$ 个正数 $a_i$(可以有相同的数字,每个数字均在 $1000$ 以内)。

输出格式

一个正整数,表示点菜方案数,保证答案的范围在 int 之内。

样例 #1

样例输入 #1

4 4
1 1 2 2

样例输出 #1

3

提示

2020.8.29,增添一组 hack 数据 by @yummy


9EB5575EBEFE4C7CBE84754DCC440B61-6-2.png

我在氵一种

很新的东西

CODE(C++)

#include <iostream>
using namespace std;

int n,m;
int a[105];
int f[10005];
int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
    }
    f[0] = 1;
    for(int i = 1;i <= n;i++){
        for(int j = m; j >= a[i]; j--){
            f[j] += f[j - a[i]];
        }
    }

    cout << f[m];
    return 0;
}


新鲜事 原文

我去 发生啥了 ???? 吓我一大跳
图片