首页 › 题库 › 信息学奥赛 › 信息学奥赛-提高级

信息学奥赛-提高级 题库

共 842 道题 ,第 39 / 43 页 · 按题型筛选,点「查看答案」核对解析
761 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.3 排列组合

贪吃蛇(snakes)

【题目描述】

草原上有 n 条蛇,编号分别为 1,2, ⋯ , n。初始时每条蛇有一个体力值ai,我们称编号为 x 的蛇实力比编号为 y 的蛇强当且仅当它们当前的体力值满足 ax > ay,或者 ax = ay 且 x > y。

接下来这些蛇将进行决斗,决斗将持续若干轮,每一轮实力最强的蛇拥有选择权,可以选择吃或者不吃掉实力最弱的蛇:

1. 如果选择吃,那么实力最强的蛇的体力值将减去实力最弱的蛇的体力值,实力最弱的蛇被吃掉,退出接下来的决斗。之后开始下一轮决斗。

2. 如果选择不吃,决斗立刻结束。

每条蛇希望在自己不被吃的前提下在决斗中尽可能多吃别的蛇(显然,蛇不会选择吃自己)。

现在假设每条蛇都足够聪明,请你求出决斗结束后会剩几条蛇。

本题有多组数据,对于第一组数据,每条蛇体力会全部由输入给出,之后的每一组数据,会相对于上一组的数据,修改一部分蛇的体力作为新的输入。

【输入格式】

输入文件名为 snakes.in。

第一行一个正整数 T,表示数据组数。

接下来有 T 组数据,对于第 1 组数据,第一行一个正整数 n,第二行 n个非负整数表示 ai。

对于第 2 组到第 T 组数据,每组数据:

第一行第一个非负整数 k 表示体力修改的蛇的个数。

第二行 2k 个整数,每两个整数组成一个二元组 (x, y),表示依次将 ax的值改为 y。一个位置可能被修改多次,以最后一次修改为准。

【输出格式】

输入文件名为 snakes.out。

输出 T 行,每行一个整数表示最终存活的蛇的条数。

【样例 1 输入】

2

3

11 14 14 

3

1 5 2 6 3 25

【样例 1 输出】

3

1

【样例 1 解释】

第一组数据,第一轮中 3 号蛇最强,1 号蛇最弱。若 3 号蛇选择吃,那么它将在第二轮被 2 号蛇吃掉。因此 3 号蛇第一轮选择不吃,3 条蛇都将存活。

对于第二组数据,3 条蛇体力变为 5,6,25。第一轮中 3 号蛇最强,1 号蛇最弱,若它选择吃,那么 3 号蛇体力值变为 20,在第二轮中依然是最强蛇并能吃掉 2 号蛇,因此 3 号蛇会选择两轮都吃,最终只有 1 条蛇存活。

【样例 2 输入】

2

5

13 31 33 39 42 

5

1 7 2 10 3 24 4 48 5 50

【样例 2 输出】

5

3

【数据范围与提示】

对于 20%的数据:n = 3。

对于 40%的数据:n ≤ 10。

对于 55%的数据:n ≤ 2000。

对于 70%的数据:n ≤ 5 × 10^4。

对于 100%的数据:3 ≤ n ≤ 10^6,1 ≤ T ≤ 10,0 ≤ k ≤ 10^5,0 ≤ ai, y ≤10^9。

保证每组数据(包括所有修改完成后的)的 ai 以不降顺序排列。

答案与解析
参考答案

#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

const int N=1e6+100,INF=1e9;

struct Node

{

    int val,num;

    #define val(i) a[i].val

    #define num(i) a[i].num

    bool operator < (const Node y)

    {

        return val==y.val?num<y.num:val<y.val;

    }

    bool operator == (const Node y)

    {

        return val==y.val && num==y.num;

    }

}a[N];

int T,n,k,ph,pb;

queue<Node> q;

Node blank={0,0},black={INF,INF};

Node Max(Node x,Node y)

{

    return (x<y)?y:x;

}

Node Min(Node x,Node y)

{

    return (x<y)?x:y;

}

bool query(Node la)

{

    int cnt=0;

    Node bk=Min(pb<ph?a[pb+1]:black,q.size()?q.back():black);

    while(1)

    {

        Node hd=Max(pb<ph?a[ph]:blank,q.size()?q.front():blank);

        if(a[ph]==hd)

            ph--;

        else

            if(q.size())

                q.pop();

        if(hd==bk)

            break;

        hd.val-=la.val;

        if(bk<hd)

            break;

        la=hd;cnt++;

    }

    return cnt&1;

}

int main()

{

    scanf("%d",&T);

    for(int i=1;i<=T;i++)

    {

        if(i==1)

        {

            scanf("%d",&n);

            for(int j=1;j<=n;j++)

                scanf("%d",&val(j)),num(j)=j;

        }

        else

        {

            scanf("%d",&k);

            for(int j=1,x,y;j<=k;j++)

            {

                scanf("%d%d",&x,&y);

                val(x)=y;

            }

        }

        ph=n,pb=1;

        while(q.size())

            q.pop();

        while(pb<=ph)

        {

            Node x=Max((ph>pb)?a[ph]:blank,q.size()?q.front():blank);

            if(a[ph]==x)

                ph--;

            else

                q.pop();

            x.val-=val(pb);

            if(x<a[pb+1] && n-pb>1)

            {

                if(query(x))

                    pb++;

                break;

            }

            q.push(x);pb++;

        }

        printf("%d\n",n-pb+1);

    }

    return 0;

}

题目详情
762 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.3 排列组合

格雷码

【题目描述】

通常,人们习惯将所有n位二进制串按照字典序排列,例如所有2位二进制串按 字典序从小到大排列为:00, 01, 10, 11

格雷码(Gray Code)是一种特殊的n位二进制串排列法,它要求相邻的两个二进 制串间恰好有一位不同.特别地,第一个串与最后一个串也算作相邻。

所有2位二进制串按格雷码排列的一个例子为:00, 01, 11, 10。

n位格雷码不止一种,下面给出其中一种格雷码的生成算法:

1.1位格雷码由两个1位二进制串组成,顺序为:0, 1。

2.n + 1位格雷码的前2^n个二进制串,可以由依此算法生成的n位格雷码(总共 2^n个n位二进制串)按顺序排列,再在每个串前加一个前缀0构成。

3.n + 1位格雷码的后2^n个二进制串,可以由依此算法生成的n位格雷码(总共 2^n个n位二进制串)按逆序排列,再在每个串前加一个前缀1构成。

综上,n + 1位格雷码,由n位格雷码的2^n个二进制串按顺序排列再加前缀0,和 按逆序排列再加前缀1构成,共2^n+1个二进制串。另外,对于n位格雷码中的2^n个 二进制串,我们按上述算法得到的排列顺序将它们从0~2^n - 1编号。

按该算法,2位格雷码可以这样推出:

1.己知1位格雷码为0, 1

2.前两个格雷码为00, 01.后两个格雷码为11, 10。合并得到00, 01, 11, 10, 编号依次为0〜3。

同理,3位格雷码可以这样推出:

1.己知2位格雷码为:00, 01, 11 10。

2.前四个格雷码为:000, 001, 011.010。后四个格雷码为:110, 111, 101, 100。合并得到:000, 001. 011, 010, 110, 111. 101, 100,编号依次为 0 ~7。

现在给出n,k请你求出按上述算法生成的n位格雷码中的k号二进制串。

【输入格式】

从文件code.in中读入数据。

仅一行两个整数n,k意义见题目描述。

【输出格式】

输出到文件code.out中。

仅一行一个n位二进制串表示答案。

【样例1输入】

23

【样例1输出】

10

【样例1解释】

2位格雷码为:00, 01, 11. 10,编号从0〜3,因此3号串是10。

【样例2输入】

35

【样例2输出】

111

【样例2解释】

3 位格雷码为:000, 001. 011, 010, 110, 111. 101, 100,编号从 0 〜7,因此 5 号串是111。

【数据范围】

对于50%的数据:n≤ 10

对于80%的数据:k≤5x10^6

对于95%的数据:k≤  2^63 - 1

对于 100% 的数据:1 ≤ n ≤ 64,0 ≤ k≤2^n

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std;


int main()

{

    int n;

    unsigned long long k;

    cin>>n>>k;

    unsigned long long s;

    for(int i=n;i>=1;i--)

    {

        s=pow(2,i);

        if(k>=(s/2))

        {

            k=s-k-1;

            printf("1");

        }

        else

            printf("0");

        

    }

    return 0;

}

题目详情
763 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

括号树

【题目背景】

本题中合法括号串的定义如下:

1.0是合法括号串。

2.如果A是合法括号串,则(A)是合法括号串。

3.如果A, B是合法括号串,则AB是合法括号串。

本题中子串与不同的子串的定义如下:

1.字符串S的子串是S中连续的任意个字符组成的字符串。S的子串可用起始位置l与终止位置r来表示,记为S(l,r)(1≤l≤r≤|S|,|S|表示S的长度)。

2.S的两个子串视作不同当且仅当它们在S中的位置不同,即l不同或r不同。

【题目描述】

一个大小为n的树包含n个结点和n-1条边,每条边连接两个结点,且任意两个 结点间有且仅有一条简单路径互相可达。

小Q是一个充满好奇心的小朋友,有一天他在上学的路上碰见了一个大小为n的 树,树上结点从1~n编号,1号结点为树的根。除1号结点外,每个结点有一个父亲 结点,u (2≤ u≤n)号结点的父亲为fu (1 ≤ fu < u)号结点。

小Q发现这个树的每个结点上恰有一个括号,可能是'('或')'。小Q定义si为:将 根结点到i号结点的简单路径上的括号,按结点经过顺序依次排列组成的字符串。

显然si是个括号串,但不一定是合法括号串,因此现在小Q想对所有的i(1≤i≤n) 求岀,si中有多少个互不相同的子串是合法括号串。

这个问题难倒了小Q,他只好向你求助。设si共有ki个不同子串是合法括号串, 你只需要告诉小Q所有ixki的异或和,即:

(1 x k1) xor (2 x k2) xor (3 x k3)xor .…xor (n x kn)其中xor是位异或运算。

【输入格式】

从文件brackets.in中读入数据。

第一行一个整数n,表示树的大小。

第二行一个长为n的由'('与')'组成的括号串,第i个括号表示i号结点上的括号。 

第三行包含n-1个整数,第i(1≤i<n)个整数表示i+1号结点的父亲编号fi+1。

【输出格式】

输出到文件brackets.out中。

 仅一行一个整数表示答案。

【样例1输入】

5

(()()

1 1 2 2

【样例1输出】

6

【样例1解释】

树的形态如下图:

将根到1号结点的简单路径上的括号,按经过顺序排列所组成的字符串为(,子串 是合法括号串的个数为0。

将根到2号结点的简单路径上的括号,按经过顺序排列所组成的字符串为((,子 串是合法括号串的个数为0。

将根到3号结点的简单路径上的括号,按经过顺序排列所组成的字符串为(),子 串是合法括号串的个数为1。

将根到4号结点的简单路径上的括号,按经过顺序排列所组成的字符串为(((,子 串是合法括号串的个数为0。

将根到5号结点的简单路径上的括号,按经过顺序排列所组成的字符串为((),子 串是合法括号串的个数为1。

【数据范围】

答案与解析
参考答案

#include <iostream>

#include <cstdio>

#include <vector>

#include <stack>

 

typedef long long ll;

const int maxn = 500005;

 

std :: vector <int> G[maxn];

std :: stack <int> bra;

 

char str[maxn];

int fa[maxn];

ll con[maxn], k[maxn];

 

void dfs(int u) {

    int num = 0;

    if (str[u] == '(')

        bra.push(u);

    else if (!bra.empty()){

        num = bra.top();

        bra.pop();

        con[u] = con[fa[num]] + 1;

    }

 

    k[u] = k[fa[u]] + con[u];

    for (int i = 0; i < G[u].size(); ++i)

        dfs(G[u][i]);

    

    if (num != 0)

        bra.push(num);

    else if (!bra.empty())

        bra.pop();

    return ;

}

 

int main() {

    int n;

    std :: scanf("%d", &n);

    std :: scanf("%s", str + 1);

    for (int i = 2; i <= n; ++i) {

        std :: scanf("%d", &fa[i]);

        G[fa[i]].push_back(i);

    }

    ll ans = 0;

    dfs(1);

    for (int i = 1; i <= n; ++i)

        ans ^= k[i] * (ll)i;

    std :: printf("%lld\n", ans);

    return 0;

}

题目详情
764 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

树上的数

【题目描述】

给定一个大小为n的树,它共有n个结点与n-1条边,结点从1~n编号。初始 时每个结点上都有一个1~n的数字,且每个1~n的数字都只在恰好一个结点上出现。

接下来你需要进行恰好n-1次删边操作,每次操作你需要选一条未被删去的边, 此时这条边所连接的两个结点上的数字将会交换.然后这条边将被删去。

n-1次操作过后,所有的边都将被删去。此时,按数字从小到大的顺序,将数字 1~n所在的结点编号依次排列,就得到一个结点编号的排列Pi。现在请你求出,在最 优操作方案下能得到的字典序最小的Pi。

如上图,蓝圈中的数字1〜5 一开始分别在结点②、①、③、⑤、④。按照⑴⑷(3)⑵ 的顺序删去所有边,树变为下图。按数字顺序得到的结点编号排列为 ①③④②⑤,该 排列是所有可能的结果中字典序最小的。

【输入格式】

从文件tree.in中读入数据。

本题输入包含多组测试数据。

第一行一个正整数T,表示数据组数。

对于每组测试数据:

第一行一个整数n,表示树的大小。

第二行n个整数,第i (1≤i≤ n)个整数表示数字i初始时所在的结点编号。 接下来n-1行每行两个整数x,y,表示一条连接x号结点与y号结点的边。

【输出格式】

输出到文件tree.out中。

对于每组测试数据,输出一行共n个用空格隔开的整数,表示最优操作方案下所 能得到的字典序最小的Pi。

【样例1输入】

4  

5

2 1 3 5 4

1 3

1 4

2 4

4 5

5

3 4 2 1 5

1 2

2 3

3 4

4 5

5

1 2 5 3 4

1 2

1 3

1 4

1 5

10

1 2 3 4 5 7 8 9 10 6

1 2

1 3

1 4

1 5

5 6

6 7

7 8

8 9

9 10

【样例1输出】

1 3 4 2 5

1  3 5 2 4

2  3 1 4 5 

2 3 4 5 6 1 7 8 9 10

【数据范围】

对于所有测试点:1 ≤ T ≤ 10,保证给出的是一个树。

答案与解析
参考答案

#include<cstdio>

#include<vector>

using namespace std;

 

#define rep(i,__l,__r) for(int i=__l,i##_end_=__r;i<=i##_end_;++i)

#define fep(i,__l,__r) for(int i=__l,i##_end_=__r;i>=i##_end_;--i)

#define writc(a,b) fwrit(a),putchar(b)

#define mp(a,b) make_pair(a,b)

#define ft first

#define sd second

#define LL long long

#define ull unsigned long long

#define pii pair<int,int>

// #define FILEOI

 

#define cg (c=getchar())

template<class T>inline void qread(T& x){

char c;bool f=0;

while(cg<'0'||'9'<c)if(c=='-')f=1;

for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));

if(f)x=-x;

}

inline int qread(){

int x=0;char c;bool f=0;

while(cg<'0'||'9'<c)if(c=='-')f=-1;

for(x=(c^48);'0'<=cg&&c<='9';x=(x<<1)+(x<<3)+(c^48));

return f?-x:x;

}

#undef cg

template<class T,class... Args>inline void qread(T& x,Args&... args){qread(x),qread(args...);}

template<class T>inline T Max(const T x,const T y){return x>y?x:y;}

template<class T>inline T Min(const T x,const T y){return x<y?x:y;}

template<class T>inline T fab(const T x){return x>0?x:-x;}

inline void getInv(int inv[],const int lim,const int MOD){

inv[0]=inv[1]=1;for(int i=2;i<=lim;++i)inv[i]=1ll*inv[MOD%i]*(MOD-MOD/i)%MOD;

}

template<class T>void fwrit(const T x){

if(x<0)return (void)(putchar('-'),fwrit(-x));

if(x>9)fwrit(x/10);putchar(x%10^48);

}

 

const int MAXN=2000;

 

struct edge{

int to,nxt;

edge(){}

edge(const int T,const int N):to(T),nxt(N){}

}e[(MAXN<<1)+5];

int tail[MAXN+5],ecnt,siz[MAXN+5];

inline void add_edge(const int u,const int v){

++siz[u],++siz[v];

e[++ecnt]=edge(v,tail[u]);tail[u]=ecnt;

e[++ecnt]=edge(u,tail[v]);tail[v]=ecnt;

}

 

int N,minp;

int pt[MAXN+5];

int pre[MAXN+5][MAXN+5],nxt[MAXN+5][MAXN+5];

//这条边的 前驱,后继

int rt[MAXN+5][MAXN+5][2];

//点 u 的某一条边的 前根节点、后根节点

int len[MAXN+5][MAXN+5];

//这条边 所在链 的链表长度

 

inline void init(){

qread(N);

ecnt=0;

rep(i,1,N)qread(pt[i]),tail[i]=siz[i]=0;

rep(i,1,N+1)rep(j,1,N+1)len[i][j]=pre[i][j]=nxt[i][j]=rt[i][j][0]=rt[i][j][1]=0;

 

int u,v;

rep(i,1,N-1){

qread(u,v);

add_edge(u,v);

pre[u][v]=pre[v][u]=nxt[u][v]=nxt[v][u]=0;

rt[u][v][0]=rt[u][v][1]=v;

rt[v][u][0]=rt[v][u][1]=u;

len[u][v]=len[v][u]=1;

}

}

 

void findPath(const int u,const int p){//当前节点、前一个节点

int a=rt[u][p][0],b=rt[u][p][1],ta,tb;

//a:来的边的前根 ; b:来的边的后根

if(p==N+1){//这是起点

for(int i=tail[u],v;i;i=e[i].nxt){//从哪条边起飞

v=e[i].to;

ta=rt[u][v][0],tb=rt[u][v][1];

if(ta!=v || (pre[u][p]==tb && len[u][ta]<siz[u]))

//条件一:如果这条边已经有一个起点且不是自己

//条件二:如果后面的那条边已经连接尾端, 且这条链的长度无法满足将所有边连起来

continue;//那么就不能把 边{u,p} 与 边{u,v} 连在一起

findPath(v,u);//否则可行

}

}

else{

if(p==b){//如果 边{u,p} 的后面还暂时没有指定必须删哪一条边, 那么就可以考虑枚举一条边接在后面

if(pre[u][N+1]==0 && (nxt[u][N+1]!=a || len[u][a]==siz[u]))//则可以考虑在点 u 进行降落, 满足以下条件:

//如果这个点的末删边还没有被指定(必须满足)

//并且:

//1.如果这条链接上开头,那么如果必须满足所有的边都在这条链上

//2.如果没有接上开头,那么长度随意

minp=Min(minp,u);//如果满足, 则 u 可以作为一个降落点

 

for(int i=tail[u],v;i;i=e[i].nxt){//假定 u 为一个中转点, 则再枚举一条边作为 边{u,p} 的出边,与其尾相连

v=e[i].to;

ta=rt[u][v][0],tb=rt[u][v][1];

if(a==ta || ta!=v || nxt[u][N+1]==v)//第一种大情况

//如果这两条边已经在同一条链上

//或者这个边不是一个起始边, 即枚举边的前面还有东西

//或者枚举边是一条起飞边, 即保证它是所有对于 u 的边必须最先删除的边

continue;//那么 当前 边{u,p} 都不能接在这条枚举边之上

if(nxt[u][N+1]==a && pre[u][N+1]==tb && len[u][a]+len[u][ta]<siz[u])

//如果这两条边分别属于这个点 最先删除、最后删除 的链表上的 尾、头

//那么它们组合起来必须等于所有边的数量之和

//否则, 这就是 提前自闭 的情况

continue;

 

findPath(v,u);//如果以上都不满足, 那么这条边是合法的

}

}

else findPath(nxt[u][p],u);//否则我们只能按照之前的规定访问这条边

}

}

 

inline void merge(const int u,const int a,const int b){

//函数条件:以 a 所在的链表为前链表

//并且满足 a 是前链表尾, b 是后链表头

int ta=rt[u][a][0],tb=rt[u][b][1];

nxt[u][a]=b;

pre[u][b]=a;

for(int i=ta;i && i!=N+1;i=nxt[u][i]){

//访问链表的基本操作

//更新每个点的前根、后根

rt[u][i][0]=ta;

rt[u][i][1]=tb;

}

len[u][ta]+=len[u][b];

}

 

bool getMark(const int u,const int p){//还原路径, 并且给路径打上标记

//如果这条路径找到终点, 返回 1, 否则返回 0

if(u==minp){//如果找到了终点

pre[u][N+1]=p;//把这条边设为最后删除的边

nxt[u][p]=N+1;//并且把这条边的下一条边标记为 N+1, 表示这条边是最后删除的

return 1;

}

int a=rt[u][p][0],b=rt[u][p][1],ta,tb;

if(p==N+1){//这是起飞点

for(int i=tail[u],v;i;i=e[i].nxt){

v=e[i].to;

ta=rt[u][v][0],tb=rt[u][v][1];

if(ta!=v || (pre[u][N+1]==tb && len[u][ta]<siz[u]))

//如果枚举边前面有东西, 那么这肯定不能接在起始边的后面, 因为它前面已经有个什么 逼 了

//或者是枚举边连接到末尾, 但是这条单链长度不够将所有的边包含到链里面

continue;//那么这条边肯定不在路径上面, 可直接跳过

if(getMark(v,u)){//如果这就是正确的路径

nxt[u][N+1]=v;//因为 u 点是起飞点, 所以把这条边记录为 u 的起飞边

pre[u][v]=N+1;//同时标记这条边的前驱, 与前面的 if 相互呼应(这不是语文...)

return 1;

}

}

}

else{//如果点 u 是中转点, 那么考虑枚举中转边

if(p==b){//如果这条边在链上后面没有其他边的时候

for(int i=tail[u],v;i;i=e[i].nxt){

v=e[i].to;

ta=rt[u][v][0],tb=rt[u][v][1];

if(a==ta || ta!=v || nxt[u][N+1]==v)//参考 findPath() 中相同位置的注释

continue;

if(nxt[u][N+1]==a && pre[u][N+1]==tb && len[u][a]+len[u][ta]<siz[u])//同样参考 findPath() 中同样位置

continue;

if(getMark(v,u)){

merge(u,p,v);//把链表合并为一个

return 1;

}

}

}

else getMark(nxt[u][p],u);

}

return 0;

}

 

signed main(){

#ifdef FILEOI

freopen("rdata.out","r",stdin);

freopen("file.out","w",stdout);

#endif

int T=qread();

while(T--){

init();

if(N==1){

writc(1,'\n');

continue;

}

rep(i,1,N){

minp=N+1;

findPath(pt[i],N+1);

// printf("%d\n",minp);

getMark(pt[i],N+1);

writc(minp,' ');

}

putchar('\n');

}

return 0;

}

题目详情
765 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.1 素数与筛法

Emiya家今天的饭

【题目描述】

Emiya 是个擅长做菜的高中生,他共掌握 n 种烹饪方法,且会使用 m 种主要食材做菜。为了方便叙述,我们对烹饪方法从 1~n 编号,对主要食材从 1 ~m 编号。

Emiya 做的每道菜都将使用恰好一种烹饪方法与恰好一种主要食材。更具体地,Emiya 会做 ai,j 道不同的使用烹饪方法 i 和主要食材 j 的菜(1 ≤i≤n,1≤j≤m),这也意味着 Emiya 总共会做

道不同的菜。

Emiya 今天要准备一桌饭招待 Yazid 和 Rin 这对好朋友,然而三个人对菜的搭配有不同的要求,更具体地,对于一种包含 k 道菜的搭配方案而言:

(1)Emiya 不会让大家饿肚子,所以将做至少一道菜,即 k≥1

(2)Rin 希望品尝不同烹饪方法做出的菜,因此她要求每道菜的烹饪方法互不相同

(3)Yazid 不希望品尝太多同一食材做出的菜,因此他要求每种主要食材至多在一半的菜(即道菜)中被使用

这里的⌊x⌋ 为下取整函数,表示不超过 x 的最大整数。

这些要求难不倒 Emiya,但他想知道共有多少种不同的符合要求的搭配方案。两种方案不同,当且仅当存在至少一道菜在一种方案中出现,而不在另一种方案中出现。

Emiya 找到了你,请你帮他计算,你只需要告诉他符合所有要求的搭配方案数对质数998,244,353 取模的结果。

【输入格式】

从文件meal.in中读入数据。

第 1 行两个用单个空格隔开的整数 n,m。

第 2 行至第 n+1 行,每行 m 个用单个空格隔开的整数,其中第 i + 1行的 m 个数依次为 ai,1,ai,2,⋯,ai,m。

【输出格式】

输出到文件meal.out中。

仅一行一个整数,表示所求方案数对 998,244,353 取模的结果。

【样例 1 输入】

2 3 

1 0 1

0 1 1

【样例 1 输出】

3

【样例1解释】

由于在这个样例中,对于每组i,j,Emiya都最多只会做一道菜,因此我们直接通 过给出烹饪方法、主要食材的编号来描述一道菜。

符合要求的方案包括:

•做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材2的菜

•做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材3的菜

•做一道用烹饪方法1、主要食材3的菜和一道用烹饪方法2、主要食材2的菜

 因此输出结果为3 mod 998,244,353 = 3。

需要注意的是,所有只包含一道菜的方案都是不符合要求的,因为唯一的主要食材 在超过一半的菜中出现,这不满足Yazid的要求。

【样例2输入】

3 3

1 2 3

4 5 0

6 0 0

【样例2输出】

190

【样例2解释】

Emiya必须至少做2道菜。

做2道菜的符合要求的方案数为100。

做3道菜的符合要求的方案数为90。

因此符合要求的方案数为100 + 90 = 190。

【样例3输入】

5 5

1 0 0 1 1

0 1 0 1 0

1 1 1 1 0

1 0 1 0 1

0 1 1 0 1

【样例3输出】

742

【数据范围】

对于所有测试点,保证 1 ≤n≤ 100, 1 ≤ m ≤ 2000, 0≤ai,j< 998,244,353。

答案与解析
参考答案

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#define mod 998244353

 

using namespace std;

typedef long long ll;

const int MAXN = 105, MAXM = 2005;

int n,m,a[MAXN][MAXM],sum[MAXN][MAXM];

ll f[MAXN][MAXN*2],g[MAXN][MAXN];

 

int main()

{

cin >> n >> m;

for(int i = 1; i<=n; i++)

    for(int j = 1; j<=m; j++)

    {

        scanf("%d",&a[i][j]);

        sum[i][0] = (sum[i][0]+a[i][j])%mod;

}

    for(int i = 1; i<=n; i++)

        for(int j = 1; j<=m; j++)

            sum[i][j] = (sum[i][0]-a[i][j]+mod)%mod;

    ll ans = 0;

    for(int col = 1; col<=m; col++)

    {

        memset(f,0,sizeof(f));

        f[0][n] = 1;

        for(int i = 1; i<=n; i++)

            for(int j = n-i; j<=n+i; j++) 

                f[i][j] = (f[i-1][j]+f[i-1][j-1]*a[i][col]%mod+f[i-1][j+1]*sum[i][col]%mod)%mod;

        for(int j = 1; j<=n; j++)

            ans = (ans+f[n][n+j])%mod;

}

g[0][0] = 1;

for(int i = 1; i<=n; i++)

    for(int j = 0; j<=n; j++) 

    g[i][j] = (g[i-1][j]+(j>0?g[i-1][j-1]*sum[i][0]%mod:0))%mod;

    for(int j = 1; j<=n; j++)

    ans = (ans-g[n][j]+mod)%mod;  

cout << ans*(mod-1)%mod << endl;

return 0;

}

题目详情
766 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.2 同余与逆元

划分

【题目描述】

2048年,第三十届CSP认证的考场上,作为选手的小明打开了第一题。这个题的 样例有n组数据,数据从1~n编号,i号数据的规模为ai。

小明对该题设计出了一个暴力程序,对于一组规模为u的数据,该程序的运行时 间为u^2。然而这个程序运行完一组规模为u的数据之后,它将在任何一组规模小于u 的数据上运行错误。样例中的ai,不一定递增,但小明又想在不修改程序的情况下正确 运行样例,于是小明决定使用一种非常原始的解决方案:将所有数据划分成若干个数据 段,段内数据编号连续,接着将同一段内的数据合并成新数据,其规模等于段内原数据 的规模之和.小明将让新数据的规模能够递增。

也就是说,小明需要找到一些分界点使得

注意P可以为0且此时k0 = 0,也就是小明可以将所有数据合并在一起运行。

小明希望他的程序在正确运行样例情况下,运行时间也能尽量小,也就是最小化

小明觉得这个问题非常有趣,并向你请教:给定n和ai,请你求出最优划分方案 下,小明的程序的最小运行时间。

【输入格式】

从文件partition.in中读入数据。

由于本题的数据范围较大,部分测试点的ai将在程序内生成。

第一行两个整数n.type. n的意义见题目描述,type表示输入方式。

1.若type = 0.则该测试点的ai直接给出。输入文件接下来:第二行n个以空格 分隔的整数ai,表示每组数据的规模。

2.若type = 1则该测试点的ai将特殊生成,生成方式见后文。输入文件接下来: 第二行六个以空格分隔的整数x,y,z,b1,b2,m。 接下来m行中,第i行包含三个以空格分隔的正整数pi,li,ri。

对于type = 1的23 ~ 25号测试点,ai的生成方式如下:

给定整数x,y,z,b1,b2,m,以及m个三元组(pi,li,ri)。

保证 n2。 若 n > 2,则

保证

对于所有则有ai=(bi   mod(rj-lj+1))+lj

上述数据生成方式仅是为了减少输入量大小,标准算法不依赖于该生成方式。

【输出格式】

输出到文件partition.out中。

输出一行一个整数,表示答案。

【样例1输入】

5 0

5 17 9 9

【样例1输出】

247

【样例1解释】

最优的划分方案为{5,1},{7},{9},{9}。由5 + 1<=7<=9<=9知该方案合法。

答案为(5 + 1)^2 + 7^2 + 9^2 + 9^2 = 247。

虽然划分方案{5},{1},{7},{9},{9}对应的运行时间比247小,但它不是一组合法 方案,因为5>1。

虽然划分方案{5},{1,7},{9},{9}合法,但该方案对应的运行时间为251,比247大。

【样例2输入】

10 0

5677462 13 19 9

【样例2输出】

1256

【样例2解释】

最优的划分方案为{5},{6},{7},{7},{4,6,2},{13},{19,9}。

【数据范围】

所有测试点满足:type € {0,1} , 2 < =n <= 4 x 10^7 , 1 < =ai,<= 10^9 , 1 <=m < =10^5 , 1 < =li <= ri <= 10^9 , 0 < x,y,z,b1,b2 < 2^30。

答案与解析
参考答案

#include<bits/stdc++.h>

using namespace std ;

const int N = 4e7 + 10 ;

const int M = 1e5 + 10 ;

const int mod = (1 << 30) ;

int n , type , x , y , z , m ;

int a[N] , b[N] , p[M] , l[M] , r[M] , q[N] , pre[N] ;

long long sum[N] ;

inline long long d(int x) { return sum[x] - sum[pre[x]] ; }

signed main() {

  ios :: sync_with_stdio(false) ; cin.tie(nullptr) ; cout.tie(nullptr) ;

  cin >> n >> type ;

  if(type) {

cin >> x >> y >> z >> b[1] >> b[2] >> m ;

    for(register int i = 1 ; i <= m ; i ++) { cin >> p[i] >> l[i] >> r[i] ; }

    for(register int i = 3 ; i <= n ; i ++) { b[i] = (0ll + 1ll * b[i - 1] * x + 1ll * b[i - 2] * y + z) % mod ; }

    for(register int i = 1 ; i <= m ; i ++)

      for(register int j = p[i - 1] + 1 ; j <= p[i] ; j ++) { a[j] = (b[j] % (r[i] - l[i] + 1)) + l[i] ; sum[j] = sum[j - 1] + a[j] ; }

}

  else {

  for(register int i = 1 ; i <= n ; i ++) { cin >> a[i] ; sum[i] = sum[i - 1] + a[i] ; }

} int h , t ; q[h = t = 0] = 0 ;

  for(register int i = 1 ; i <= n ; i ++) {

    while(h < t && d(q[h + 1]) + sum[q[h + 1]] <= sum[i]) ++ h ; 

pre[i] = q[h] ;

    while(h < t && d(q[t]) + sum[q[t]] >= d(i) + sum[i]) -- t ;

    q[++ t] = i ;

  }  int now = n ; __int128 ans = 0 , tmp = 1 ;

while(now) { tmp = d(now) ; tmp *= d(now) ; ans += tmp ; now = pre[now] ; }

int st[50] , tp = 0 ;

while(ans) { st[++ tp] = ans % 10 ; ans /= 10 ; }

while(tp) { cout << st[tp --] ; }

  return 0 ;

}

题目详情
767 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

树的重心

小简单正在学习离散数学,今天的内容是图论基础,在课上他做了如下两条笔记:

1.一个大小为n的树由n个结点与n-1条无向边构成,且满足任意两个结点间有 且仅有一条简单路径。在树中删去一个结点及与它关联的边,树将分裂为若干个 子树;而在树中删去一条边(保留关联结点,下同),树将分裂为恰好两个子树。

2.对于一个大小为n的树与任意一个树中结点c,称c是该树的重心当且仅当在树 中删去c及与它关联的边后,分裂出的所有子树的大小均不超过(其中Lx」 是下取整函数)。对于包含至少一个结点的树.它的重心只可能有1或2个。

课后老师给出了一个大小为n的树S,树中结点从1~n编号。小简单的课后作业 是求出S单独删去每条边后,分裂出的两个子树的重心编号和之和。即:

上式中,E表示树S的边集,(u,n)表示一条连接u号点和V号点的边。S'u与S'v 分别表示树S删去边(u,v)后,u号点与V号点所在的被分裂出的子树。

小简单觉得作业并不简单,只好向你求助,请你教教他。

【输入格式】

从文件centroid.in中读入数据。

本题输入包含多组测试数据。

第一行一个整数T表示数据组数。

接下来依次给岀每组输入数据,对于每组数据:

第一行一个整数n表示树S的大小。

接下来n -1行,每行两个以空格分隔的整数 ui,vi,表示树中的一条边(ui,vi)。

【输出格式】

输出到文件centroid.out中。

共T行,每行一个整数.第i行的整数表示:第i组数据给岀的树单独删去每条边 后,分裂出的两个子树的重心编号和之和。

【样例1输入】

2

5

12

23

24

35

7

1 2

1 3

1 4

3 5

3 6

6 7

【样例1输出】

32

56

【样例1解释】

对于第一组数据:

删去边(1,2), 1号点所在子树重心编号为{1}, 2号点所在子树重心编号为{2,3}。 删去边(2,3), 2号点所在子树重心编号为⑵,3号点所在子树重心编号为{3,5}。

删去边(2,4), 2号点所在子树重心编号为{2,3}, 4号点所在子树重心编号为{4}。 删去边(3,5), 3号点所在子树重心编号为{2}, 5号点所在子树重心编号为{5}。

因此答案为 1 + 2 + 3 + 2 + 3 + 5 + 2 + 3 + 4 + 2 + 5 = 32。

【数据范围】

表中特殊性质一栏,两个变量的含义为存在一个1~n的排列使得: 

A:树的形态是一条链。即存在一条边(pi,pi+1)。

B:树的形态是一个完美二叉树。即存在两条边(Pi,P2i)与(Pi,P2i+1)。 对于所有测试点:保证给岀的图是一个树。

答案与解析
参考答案

#include <cstdio>

#include <algorithm>

using namespace std;


const int Maxn = 300000;

const int Maxlog = 19;

typedef long long ll;


#ifdef LOACL

bool ___;

#endif


struct Edge {

int to;

Edge *nxt;

};

Edge pool[Maxn * 2 + 5];

Edge *G[Maxn + 5], *ecnt;

inline void addedge(int u, int v) {

Edge *p = ++ecnt;

p->to = v, p->nxt = G[u];

G[u] = p;

}


int N;

int siz[Maxn + 5];

int mxson[Maxn + 5], mx2son[Maxn + 5];

ll ans;


int s[Maxn + 1][Maxlog + 2];

int f[Maxn + 5];


inline void clear() {

for(int i = 1; i <= N; i++)

mxson[i] = mx2son[i] = 0;

for(int i = 1; i <= N; i++)

for(int j = 0; j <= Maxlog; j++)

s[i][j] = 0;

for(int i = 1; i <= N; i++)

G[i] = NULL;

ecnt = &pool[0];

ans = 0;

}

inline void modify(int u) {

for(int i = 1; i <= Maxlog; i++)

s[u][i] = s[s[u][i - 1]][i - 1];

}

void PreDFS(int u, int fa) {

siz[u] = 1, f[u] = fa;

for(Edge *p = G[u]; p != NULL; p = p->nxt) {

int v = p->to;

if(v == fa) continue;

PreDFS(v, u);

siz[u] += siz[v];

if(siz[v] > siz[mxson[u]]) {

mx2son[u] = mxson[u];

mxson[u] = v;

} else if(siz[v] > siz[mx2son[u]])

mx2son[u] = v;

}

s[u][0] = mxson[u];

modify(u);

}

inline void calc(int u) {

int tot = siz[u], rt = u;

for(int i = Maxlog; i >= 0; i--)

if(tot - siz[s[u][i]] <= tot / 2)

u = s[u][i];

if(siz[s[u][0]] <= tot / 2) ans += u;

if(u != rt && siz[u] <= tot / 2) ans += f[u];

}

void DFS(int u, int fa) {

if(fa != 0) calc(fa), calc(u);

int flag = 0, t1;

if(N - siz[u] > siz[mxson[u]]) {

t1 = mx2son[u], flag = 1;

mx2son[u] = mxson[u], mxson[u] = fa;

} else if(N - siz[u] > siz[mx2son[u]]){

t1 = mx2son[u], flag = 2;

mx2son[u] = fa;

}

for(Edge *p = G[u]; p != NULL; p = p->nxt) {

int v = p->to;

if(v == fa) continue;

siz[u] += siz[fa] - siz[v], f[u] = v;

if(v == mxson[u]) s[u][0] = mx2son[u];

else s[u][0] = mxson[u];

modify(u);

DFS(v, u);

siz[u] -= siz[fa] - siz[v], f[u] = fa;

}

if(flag == 1) {

mxson[u] = mx2son[u], mx2son[u] = t1;

} else if(flag == 2) mx2son[u] = t1;

s[u][0] = mxson[u];

modify(u);

}


#ifdef LOACL

bool ____;

#endif


int main() {

#ifdef LOACL

freopen("in.txt", "r", stdin);

freopen("out.txt", "w", stdout);

#endif

int _;

scanf("%d", &_);

while(_--) {

scanf("%d", &N);

clear();

for(int i = 1; i < N; i++) {

int u, v;

scanf("%d %d", &u, &v);

addedge(u, v), addedge(v, u);

}

PreDFS(1, 0);

DFS(1, 0);

printf("%lld\n", ans);

}

#ifdef LOACL

printf("%.2f\n", (&____ - &___) / 1048576.0);

#endif

return 0;

}

题目详情
768 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

铺设道路

【问题描述】

春春是一名道路工程师,负责铺设一条长度为 n 的道路。

铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n 块首尾相连的区域,一开始,第 i 块区域下陷的深度为 di 。

春春每天可以选择一段连续区间 [L, R] ,填充这段区间中的每块区域,让其下陷深度减少 1。在选择区间时,需要保证,区间内的每块区域在填充前下陷深度均不为 0 。

春春希望你能帮他设计一种方案,可以在最短的时间内将整段道路的下陷深度都变为 0 。

【输入格式】

输入文件名为 road.in。

输入文件包含两行,第一行包含一个整数 n,表示道路的长度。

第二行包含 n 个整数,相邻两数间用一个空格隔开,第 i 个整数为 di 。

【输出格式】

输出文件名为 road.out。

输出文件仅包含一个整数,即最少需要多少天才能完成任务。

【输入输出样例 1】

【样例解释】

一种可行的最佳方案是,依次选择:

[1,6]、[1,6]、[1,2]、[1,1]、[4,6]、[4,4]、[4,4]、[6,6]、[6,6]。

【数据规模与约定】

对于 30% 的数据,1 ≤ n ≤ 10 ;

对于 70% 的数据,1 ≤ n ≤ 1000 ;

对于 100% 的数据,1 ≤ n ≤ 100000 ,0 ≤ di ≤ 10000 。

答案与解析
参考答案

#include <bits/stdc++.h>

#define inf 0x3f3f3f3f

using namespace std;

int ans,d[100001],N;

int partition1(int left, int right) //分治(实现这一片区域的操作)

{   int sum1=0;

if(left>=right) //当不能再分时返回

{  

if(left==right) //如果区域是单个数

{   int t=d[left];

d[left]=0; //清0

return t; //直接返回里面的值(它里面的值代表这个单个区域需要的天数)

}

else

return 0;

}   

int min1=inf,l=left;

for (int i=left; i<=right;i++) //求出这片区域的最小值

    min1=min(d[i],min1);

sum1+=min1;//先把最小值加上

for(int i=left; i<=right; i++)

{  d[i]-=min1; //每个都减去最小值

   if(d[i]==0&&d[i-1]!=0) //如果遇到0分界线

           {

   sum1+=partition1(l,i-1);//把之前的区域分治

   }

   if(d[i]!=0&&d[i-1]==0) l=i;//如果在0之后遇到新的左端点,更新

}

if(d[right]!=0)//不要忘掉最后一块区域

sum1+=partition1(l,right);

return sum1;

}

int main()

{

//freopen("in.txt","r",stdin);

cin>>N;

for(int i=1;i<=N;i++)

cin>>d[i];

ans=partition1(1,N);

cout<<ans;

return 0;

 } 

题目详情
769 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

货币系统

【问题描述】

在网友的国度中共有 n 种不同面额的货币,第 i 种货币的面额为 a[i],你可以假设每一种货币都有无穷多张。为了方便,我们把货币种数为 n、面额数组为 a[1..n]的货币系统记作 (n,a)。

在一个完善的货币系统中,每一个非负整数的金额 x 都应该可以被表示出,即对每一个非负整数 x,都存在 n 个非负整数 t[i] 满足 a[i]× t[i] 的和为 x。然而,在网友的国度中,货币系统可能是不完善的,即可能存在金额 x 不能被该货币系统表示出。例如在货币系统 n=3, a=[2,5,9] 中,金额 1,3 就无法被表示出来。

两个货币系统 (n,a) 和 (m,b) 是等价的,当且仅当对于任意非负整数 x,它要么均可以被两个货币系统表出,要么不能被其中任何一个表出。

现在网友们打算简化一下货币系统。他们希望找到一个货币系统 (m,b),满足(m,b) 与原来的货币系统 (n,a) 等价,且 m 尽可能的小。他们希望你来协助完成这个艰巨的任务:找到最小的 m。

【输入格式】

输入文件名为 money.in。

输入文件的第一行包含一个整数 T,表示数据的组数。接下来按照如下格式分别给出 T 组数据。

每组数据的第一行包含一个正整数 n。接下来一行包含 n 个由空格隔开的正整数a[i]。

【输出格式】

输出文件名为 money.out。

输出文件共有 T 行,对于每组数据,输出一行一个正整数,表示所有与 (n,a) 等价的货币系统 (m,b) 中,最小的 m。

【输入输出样例 1】

【输入输出样例 1 说明】

在第一组数据中,货币系统 (2, [3,10]) 和给出的货币系统 (n, a) 等价,并可以验证不存在 m < 2 的等价的货币系统,因此答案为 2。

在第二组数据中,可以验证不存在 m < n 的等价的货币系统,因此答案为 5。

【数据规模与约定】

对于 100% 的数据,满足 1 ≤ T ≤ 20, n,a[i] ≥ 1。

答案与解析
参考答案

#include<iostream>

#include<algorithm>

#include<cstring>

#define N 25005

using namespace std;

bool dp[N]={0};

int a[103]={0};

int T=0,n=0;

int ret=0;

int main()

{

    cin>>T;

    while(T--)

    {

        cin>>n;

        ret=0;

        memset(dp,0,sizeof(dp));

        dp[0]=1;

        for(int i=1;i<=n;i++) 

            cin>>a[i];

        sort(a+1,a+1+n);

        for(int i=1;i<=n;i++)

        {

            if(dp[a[i]]) 

                continue;

            ret++;

            for(int j=a[i];j<=a[n];j++)

            {

                dp[j]|=dp[j-a[i]];

            }

        }

        cout<<ret<<endl;

    }

    return 0;

}

题目详情
770 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

赛道修建

【问题描述】

C 城将要举办一系列的赛车比赛。在比赛前,需要在城内修建m 条赛道。

C 城一共有 n 个路口,这些路口编号为 1,2, … , n,有 n − 1 条适合于修建赛道的双向通行的道路,每条道路连接着两个路口。其中,第 i 条道路连接的两个路口编号为 ai和 bi,该道路的长度为 li。借助这 n − 1 条道路,从任何一个路口出发都能到达其他所有的路口。

一条赛道是一组互不相同的道路 e1, e2, … , ek,满足可以从某个路口出发,依次经过道路 e1, e2, … , ek(每条道路经过一次,不允许调头)到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全,要求每条道路至多被一条赛道经过。

目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案,使得修建的m条赛道中长度最小的赛道长度最大(即m条赛道中最短赛道的长度尽可能大)。

【输入格式】

输入文件名为 track.in。

输入文件第一行包含两个由空格分隔的正整数 n, m,分别表示路口数及需要修建的赛道数。

接下来 n − 1 行,第 i 行包含三个正整数 ai, bi, li,表示第 i 条适合于修建赛道的道路连接的两个路口编号及道路长度。保证任意两个路口均可通过这 n − 1 条道路相互到达。每行中相邻两数之间均由一个空格分隔。

【输出格式】

输出文件名为 track.out。

输出共一行,包含一个整数,表示长度最小的赛道长度的最大值。

【输入输出样例 1】

【输入输出样例 1 说明】

所有路口及适合于修建赛道的道路如下图所示:

道路旁括号内的数字表示道路的编号,非括号内的数字表示道路长度。

需要修建 1 条赛道。可以修建经过第 3,1,2,6 条道路的赛道(从路口 4 到路口 7),则该赛道的长度为 9 + 10 + 5 + 7 = 31,为所有方案中的最大值。

【输入输出样例 2】

【输入输出样例 2 说明】

所有路口及适合于修建赛道的道路如下图所示:

需要修建 3 条赛道。可以修建如下 3 条赛道:

1. 经过第 1,6 条道路的赛道(从路口 1 到路口 7),长度为 6 + 9 = 15;

2. 经过第 5,2,3,8 条道路的赛道(从路口 6 到路口 9),长度为 4 + 3 + 5 + 4 = 16;

3. 经过第 7,4 条道路的赛道(从路口 8 到路口 5),长度为 7 + 10 = 17。

长度最小的赛道长度为 15,为所有方案中的最大值。

【数据规模与约定】

所有测试数据的范围和特点如下表所示

其中,“分支不超过 3”的含义为:每个路口至多有 3 条道路与其相连。对于所有的数据,2 ≤ n≤ 50,000,1 ≤ m ≤ n − 1,1 ≤ ai, bi ≤ n,1 ≤ li ≤ 10,000。

答案与解析
参考答案

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <set>

#include <vector>

using namespace std;


int head[50100],to[100100],nex[100100],val[100100];

int n,waysnumber,m,edges;


multiset <int> :: iterator it;


int dfs(int now,int father,int x){

multiset <int> son;

for (int v = head[now]; v ; v = nex[v])

if (to[v] != father){

int tmpways = dfs(to[v],now,x) + val[v];

if (tmpways >= x) ++waysnumber;

else son.insert(tmpways);

}

//对当前点now的所有子路径进行组合,用刚好能满足≥x的最小的边组合

//并返回所有儿子中最长的无法被组合成满足条件路的点 

int maxwaylen = 0;

while (son.size() > 1){

it = son.lower_bound(x - *son.begin());

if (it == son.begin()) it++; //若最短的边≥x的时候,则用最短的两条边组合 

if (it == son.end()){        //当前最短的边没办法找到够长的边组合出满足条件的路 

//挑一条最长的子边返回 

maxwaylen = max(maxwaylen,*son.begin());

son.erase(son.begin());

}

else{

//成功组合出了满足条件的边 

++waysnumber;

son.erase(it);

son.erase(son.begin());

}

}

if (son.size() == 1) maxwaylen = max(maxwaylen,*son.begin());

return maxwaylen;

}

 

bool check(int x){

waysnumber = 0;

dfs(1,0,x);

if (waysnumber >= m) return true;

else return false;

}


void addedge(int u,int v,int c){

    nex[++edges] = head[u], head[u] = edges, to[edges] = v, val[edges] = c;

}


int main()

{

edges = 0;

scanf("%d%d",&n,&m);

long long all = 0;

for (int i = 1 ; i < n ; ++i){

int a,b,c;scanf("%d%d%d",&a,&b,&c);

addedge(a,b,c);

addedge(b,a,c);

all += c;

}

int l = 0 , r = all / m,mid,ans;   //这里存在一个坑,对于ai = 1的图,如果这里的 r 使用极大值500000000,就会超时

while (l <= r){

mid = (l + r) >> 1;

if (check(mid)) ans = mid,l = mid + 1;

else r = mid - 1;

}

printf("%d\n",ans);

return 0;

} 

题目详情
771 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

旅行

【问题描述】

小 Y 是一个爱好旅行的 OIer。她来到 X 国,打算将各个城市都玩一遍。

小 Y 了解到,X 国的n 个城市之间有 m 条双向道路。每条双向道路连接两个城市。不存在两条连接同一对城市的道路,也不存在一条连接一个城市和它本身的道路。并且,从任意一个城市出发,通过这些道路都可以到达任意一个其他城市。小 Y 只能通过这些道路从一个城市前往另一个城市。

小 Y 的旅行方案是这样的:任意选定一个城市作为起点,然后从起点开始,每次可以选择一条与当前城市相连的道路,走向一个没有去过的城市,或者沿着第一次访问该城市时经过的道路后退到上一个城市。当小 Y 回到起点时,她可以选择结束这次旅行或继续旅行。需要注意的是,小 Y 要求在旅行方案中,每个城市都被访问到。

为了让自己的旅行更有意义,小 Y 决定在每到达一个新的城市(包括起点)时,将它的编号记录下来。她知道这样会形成一个长度为n 的序列。她希望这个序列的字典序最小,你能帮帮她吗?

对于两个长度均为 n 的序列 A 和 B,当且仅当存在一个正整数 x,满足以下条件时,我们说序列 A 的字典序小于 B。

⚫ 对于任意正整数 1 ≤ i < x,序列 A 的第 i 个元素 Ai 和序列 B 的第 i 个元素Bi 相同。

⚫ 序列 A 的第 x 个元素的值小于序列 B 的第 x 个元素的值。

【输入格式】

输入文件名为 travel.in。

输入文件共 m + 1 行。第一行包含两个整数 n, m(m ≤ n) ,中间用一个空格分隔。

接下来 m 行,每行包含两个整数 u, v (1 ≤ u, v ≤ n) ,表示编号为 u 和 v 的城市之间有一条道路,两个整数之间用一个空格分隔。

【输出格式】

输出文件名为 travel.out。

输出文件包含一行,n 个整数,表示字典序最小的序列。相邻两个整数之间用一个空格分隔。

【输入输出样例 1】

【输入输出样例 2】

【数据规模与约定】

对于 100% 的数据和所有样例,1 ≤ n ≤ 5000 且 m = n − 1 或 m = n 。

对于不同的测试点,我们约定数据的规模如下:

答案与解析
参考答案

#include<bits/stdc++.h>

#define maxn 50500

using namespace std;

inline int read() {

int x=0;char c=getchar();

while(!isdigit(c)) c=getchar();

while(isdigit(c)) x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}


int n,m,cnt,del;

int ans[maxn],start[maxn],to[maxn],cur[maxn];

vector<int> v[maxn];


inline bool check() {

if(cnt != n) return false;

for(int i=1;i<=n;i++) if(cur[i]!=ans[i]) return ans[i]>cur[i];

}

void dfs(int u,int f) {

if(cnt>n) return ;

cur[++cnt]=u;

for(int i=0;i<v[u].size();i++) {

if(v[u][i]==f || (u==start[del]&&v[u][i]==to[del]) || (v[u][i]==start[del]&&u==to[del])) continue;

dfs(v[u][i],u);

}

}

int main() {

//freopen("test.in","r",stdin);

//freopen("test.out","w",stdout);

memset(ans,64,sizeof(ans));

n=read(),m=read();

for(int i=1;i<=m;i++) {

int x=read(),y=read();

v[x].push_back(y);

v[y].push_back(x);

start[i]=x;to[i]=y;

}

for(int i=1;i<=n;i++) sort(v[i].begin(),v[i].end());

if(m==n-1) {

del=0;cnt=0;

dfs(1,0);

memcpy(ans,cur,sizeof(cur));

} else {

for(int i=1;i<=m;i++) {

memset(cur,0,sizeof(cur));

del=i;cnt=0;

dfs(1,0);

if(check() ) {

memcpy(ans,cur,sizeof(cur));

}

}

}

for(int i=1;i<=n;i++) printf("%d ",ans[i]);

return 0;

}

题目详情
772 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

 填数游戏

【问题描述】

小 D 特别喜欢玩游戏。这一天,他在玩一款填数游戏。

这个填数游戏的棋盘是一个n × m的矩形表格。玩家需要在表格的每个格子中填入一个数字(数字 0 或者数字 1),填数时需要满足一些限制。

下面我们来具体描述这些限制。

为了方便描述,我们先给出一些定义:

• 我们用每个格子的行列坐标来表示一个格子,即(行坐标,列坐标)。(注意:行列坐标均从 0 开始编号)

• 合法路径 P:一条路径是合法的当且仅当:

1. 这条路径从矩形表格的左上角的格子(0,0)出发,到矩形的右下角格子(n − 1, m − 1)结束;

2. 在这条路径中,每次只能从当前的格子移动到右边与它相邻的格子,或者从当前格子移动到下面与它相邻的格子。

例如:在下面这个矩形中,只有两条路径是合法的,它们分别是p1:(0,0) → (0,1) →(1,1)和p2:(0,0) → (1,0) → (1,1)。

对于一条合法的路径 P,我们可以用一个字符串w(P)来表示,该字符串的长度为n +m − 2,其中只包含字符“R”或者字符“D”,第 i 个字符记录了路径 P 中第 i 步的移动方法,“R”表示移动到当前格子右边与它相邻的格子,“D”表示移动到当前格子下面与它相邻的格子。例如,上图中对于路径p1,有w(P1) = "RD";而对于另一条路径p2,有w(P2) = "DR"。

同时,将每条合法路径 P 经过的每个格子上填入的数字依次连接后,会得到一个长度为n + m − 1的 01 字符串,记为 s(P)。例如,如果我们在格子(0,0)和(1,0)上填入数字0,在格子(0,1)和(1,1)上填入数字 1(见上图红色数字)。那么对于路径p1,我们可以得到s(P1) = "011",对于路径p2,有s(P2) = "001"。

游戏要求小 D 找到一种填数字 0、1 的方法,使得对于两条路径p1,P2,如果w(P1) >w(P2),那么必须s(P1) ≤ s(P2)。我们说字符串 a 比字符串 b 小,当且仅当字符串 a 的字典序小于字符串 b 的字典序,字典序的定义详见第一题。但是仅仅是找一种方法无法满足小 D 的好奇心,小 D 更想知道这个游戏有多少种玩法,也就是说,有多少种填数字的方法满足游戏的要求?

小 D 能力有限,希望你帮助他解决这个问题,即有多少种填 0、1 的方法能满足题目要求。由于答案可能很大,你需要输出答案对109 + 7取模的结果。

【输入格式】

输入文件名为 game.in。

输入文件共一行,包含两个正整数 n、m,由一个空格分隔,表示矩形的大小。其中 n 表示矩形表格的行数,m 表示矩形表格的列数。

【输出格式】

输出文件名为 game.out。

输出共一行,包含一个正整数,表示有多少种填 0、1 的方法能满足游戏的要求。

注意:输出答案对 10^9+7 取模的结果。

【输入输出样例 1】

【样例解释】

对于2 × 2棋盘,有上图所示的 12 种填数方法满足要求。

【输入输出样例 2】

【输入输出样例 3】

【数据规模与约定】

答案与解析
参考答案

#include<cstdio>

#include<cstring>

#include<algorithm>

#define P 1000000007

using namespace std;

int n,m,inv128=570312504,inv384=190104168;

int add(int x,int y)  {return x+y>=P?x+y-P:x+y;}

int dec(int x,int y)  {return x-y< 0?x-y+P:x-y;}

int mul(int x,int y)  {return 1ll*x*y%P;}

int power(int a,int b){

int ans=1;

for(;b;b>>=1,a=mul(a,a))  if(b&1)  ans=mul(ans,a);

return ans;

}

int main(){

scanf("%d%d",&n,&m);

if(n>m)  swap(n,m);

if(n==1)  printf("%d\n",power(2,m));

else  if(n==2)  printf("%d\n",mul(4,power(3,m-1)));

else  if(n==3)  printf("%d\n",mul(112,power(3,m-3)));

else{

if(m==n)  printf("%d\n",(83ll*power(8,n)%P+5ll*power(2,n+7)%P)*inv384%P);

else  printf("%d\n",(83ll*power(8,n)%P+power(2,n+8))*power(3,m-n-1)%P*inv128%P);

}

return 0;

}

题目详情
773 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

保卫王国

【问题描述】

Z 国有n座城市,n − 1条双向道路,每条双向道路连接两座城市,且任意两座城市都能通过若干条道路相互到达。

Z 国的国防部长小 Z 要在城市中驻扎军队。驻扎军队需要满足如下几个条件:

一座城市可以驻扎一支军队,也可以不驻扎军队。

由道路直接连接的两座城市中至少要有一座城市驻扎军队。

在城市里驻扎军队会产生花费,在编号为i的城市中驻扎军队的花费是pi。

小 Z 很快就规划出了一种驻扎军队的方案,使总花费最小。但是国王又给小 Z 提出了m个要求,每个要求规定了其中两座城市是否驻扎军队。小 Z 需要针对每个要求逐一给出回答。具体而言,如果国王提出的第j个要求能够满足上述驻扎条件(不需要考虑第 j 个要求之外的其它要求),则需要给出在此要求前提下驻扎军队的最小开销。如果国王提出的第j个要求无法满足,则需要输出-1 (1 ≤ j ≤ m)。现在请你来帮助小 Z。

【输入格式】

输入文件名为 defense.in。

第 1 行包含两个正整数n, m和一个字符串type,分别表示城市数、要求数和数据类型。type是一个由大写字母 A,B 或 C 和一个数字 1,2,3 组成的字符串。它可以帮助你获得部分分。你可能不需要用到这个参数。这个参数的含义在【数据规模与约定】中有具体的描述。

第2行n个整数pi,表示编号i的城市中驻扎军队的花费。

接下来n − 1行,每行两个正整数u, v,表示有一条u到v的双向道路。

接下来m行,第j行四个整数a, x, b, y(a ≠ b),表示第j个要求是在城市a驻扎x支军队,在城市b驻扎y支军队。其中,x 、 y 的取值只有 0 或 1:若 x 为 0,表示城市 a 不得驻扎军队,若 x 为 1,表示城市 a 必须驻扎军队;若 y 为 0,表示城市 b 不得驻扎军队,若 y 为 1,表示城市 b 必须驻扎军队。

输入文件中每一行相邻的两个数据之间均用一个空格分隔。

【输出格式】

输出文件名为 defense.out。

输出共m行,每行包含 1 个整数,第j行表示在满足国王第j个要求时的最小开销,如果无法满足国王的第j个要求,则该行输出-1。

【输入输出样例 1】

【样例解释】

对于第一个要求,在 4 号和 5 号城市驻扎军队时开销最小。

对于第二个要求,在 1 号、2 号、3 号城市驻扎军队时开销最小。

第三个要求是无法满足的,因为在 1 号、5 号城市都不驻扎军队就意味着由道路直接连

接的两座城市中都没有驻扎军队。

【数据规模与约定】

对于 100%的数据,n, m ≤ 300000,1 ≤ pi ≤ 100000。

数据类型的含义:

A:城市i与城市i + 1直接相连。

B:任意城市与城市 1 的距离不超过 100(距离定义为最短路径上边的数量),即如果这棵树以 1 号城市为根,深度不超过 100。

C:在树的形态上无特殊约束。

1:询问时保证a = 1, x = 1,即要求在城市 1 驻军。对b, y没有限制。

2:询问时保证a, b是相邻的(由一条道路直接连通)

3:在询问上无特殊约束。

答案与解析
参考答案

#pragma GCC optimize("O3")

#pragma G++ optimize("O3")

#include<stdio.h>

#include<string.h>

#include<algorithm>

#define MAXN 100005

#define MAXM MAXN*2

#define ll long long

#define reg register ll

#define INF 1000000000000000007ll

#define fo(i,a,b) for (reg i=a;i<=b;++i)

#define fd(i,a,b) for (reg i=a;i>=b;--i)

#define rep(i,a) for (reg i=last[a];i;i=next[i])

#define O3 __attribute__((optimize("-O3")))


ll last[MAXM],next[MAXM],tov[MAXM];

ll p[MAXN],depth[MAXN],fa[MAXN];

ll f[MAXN][2],g[MAXN][2];

ll anc[MAXN][21];

ll n,m,tot,ans;

char type[5];


struct node

{

ll a[2][2];

}dis[MAXN][21],A,B,C;


O3 inline ll read()

{

ll x=0,f=1;char ch=getchar();

while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}

while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();

return x*f;

}

O3 inline ll min(ll x,ll y)

{

return x<y?x:y;

}

O3 inline void swap(ll &x,ll &y)

{

x=x+y,y=x-y,x=x-y;

}

O3 inline void link(ll x,ll y)

{

next[++tot]=last[x],last[x]=tot,tov[tot]=y;

}

O3 inline void dfs1(ll x)

{

depth[x]=depth[fa[x]]+1,anc[x][0]=fa[x];

fo(i,1,20)anc[x][i]=anc[anc[x][i-1]][i-1];

f[x][0]=0,f[x][1]=p[x];

rep(i,x)if (tov[i]!=fa[x])

{

fa[tov[i]]=x,dfs1(tov[i]);

f[x][0]+=f[tov[i]][1];

f[x][1]+=min(f[tov[i]][0],f[tov[i]][1]);

}

}

O3 inline void dfs2(ll x)

{

if (x==1)g[x][0]=f[x][0],g[x][1]=f[x][1];

else

{

g[x][0]=f[x][0]+g[fa[x]][1]-min(f[x][0],f[x][1]);

g[x][1]=f[x][1]+min(g[fa[x]][0]-f[x][1],g[fa[x]][1]-min(f[x][0],f[x][1]));

}

rep(i,x)if (tov[i]!=fa[x])

{

dis[tov[i]][0].a[0][0]=INF;

dis[tov[i]][0].a[1][0]=f[x][0]-f[tov[i]][1];

dis[tov[i]][0].a[0][1]=f[x][1]-min(f[tov[i]][0],f[tov[i]][1]);

dis[tov[i]][0].a[1][1]=f[x][1]-min(f[tov[i]][0],f[tov[i]][1]);

dfs2(tov[i]);

}

}

O3 inline node merge(node A,node B)

{

memset(C.a,60,sizeof(C.a));

fo(i,0,1)fo(j,0,1)fo(k,0,1)

C.a[i][j]=min(C.a[i][j],A.a[i][k]+B.a[k][j]);

return C;

}

O3 int main()

{

freopen("defense.in","r",stdin);

freopen("defense.out","w",stdout);

//freopen("readin.txt","r",stdin);

n=read(),m=read(),scanf("%s",&type);

fo(i,1,n)p[i]=read();

fo(i,1,n-1)

{

ll x=read(),y=read();

link(x,y),link(y,x);

}

dfs1(1),dfs2(1);

fo(j,1,20)fo(i,1,n)dis[i][j]=merge(dis[i][j-1],dis[anc[i][j-1]][j-1]);

while (m--)

{

ll a=read(),x=read(),b=read(),y=read();

if (x+y==0 && ((fa[a]==b) || (fa[b]==a)))

{

printf("-1\n");

continue;

}

if (depth[a]<depth[b])swap(a,b),swap(x,y);

memset(A.a,60,sizeof(A.a));

memset(B.a,60,sizeof(B.a));

A.a[x][x]=f[a][x],B.a[y][y]=f[b][y];

fd(i,20,0)if (depth[anc[a][i]]>depth[b])

{

A=merge(A,dis[a][i]),a=anc[a][i];

}

if (fa[a]==b)

{

printf("%lld\n",y==0?g[b][0]-f[a][1]+A.a[x][1]:

g[b][1]-min(f[a][0],f[a][1])+min(A.a[x][0],A.a[x][1]));

continue;

}

if (depth[a]!=depth[b])A=merge(A,dis[a][0]),a=fa[a];

fd(i,20,0)if (anc[a][i]!=anc[b][i])

{

A=merge(A,dis[a][i]),B=merge(B,dis[b][i]);

a=anc[a][i],b=anc[b][i];

}

printf("%lld\n",min(g[fa[a]][0]-f[a][1]-f[b][1]+A.a[x][1]+B.a[y][1],

g[fa[a]][1]-min(f[a][0],f[a][1])-min(f[b][0],f[b][1])+min(A.a[x][0],A.a[x][1])+min(B.a[y][0],B.a[y][1])));

}

return 0;

}

题目详情
774 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

NOIP 初赛中,选手可以带入考场的有( )。

答案与解析
正确答案:A,B
这道题暂未补解析。
题目详情
775 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

2-3 树是一种特殊的树,它满足两个条件:

(1)每个内部结点有两个或三个子结点;

(2)所有的叶结点到根的路径长度相同。

如果一棵 2-3 树有 10 个叶结点,那么它可能有( )个非叶结点。

答案与解析
正确答案:C,D
这道题暂未补解析。
题目详情
776 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 4.2 最短路径

下列关于最短路算法的说法正确的有( )。

答案与解析
正确答案:A,B,D
这道题暂未补解析。
题目详情
777 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

下列说法中,是树的性质的有( )。

答案与解析
正确答案:A,B,D
这道题暂未补解析。
题目详情
778 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

下列关于图灵奖的说法中,正确的有( )。

答案与解析
正确答案:B,C,D
这道题暂未补解析。
题目详情
779 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

甲乙丙丁四人在考虑周末要不要外出郊游。

已知:①如果周末下雨,并且乙不去,则甲一定不去;②如果乙去,则丁一定去;③如果丙去,则丁一定不去;④如果丁不去,而且甲不去,则丙一定不去。如果周末丙去了,则甲________(去了/没去)(1 分),乙________(去了/没去)(1 分),丁________(去了/没去)(1 分),周末________(下雨/没下雨)(2 分)。

答案与解析
参考答案

去了 没去 没去 没下雨 (第4 空 2 分,其余 1 分)

题目详情
780 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

方程 a*b = (a or b) * (a and b),在 a,b 都取 [0, 31] 中的整数时,共有_____组解。(*表示乘法;or 表示按位或运算;and 表示按位与运算)

答案与解析
参考答案

共有454组解

题目详情