2019.4.6高中部集训

课程表

上午

  • 考试$QAQ$

下午

  • 考试$QAQ$

晚上

  • 讲评考试$QAQ$(其实在听讲座)

考试

上午

  1. 刷题计划(problem.cpp/problem.in/problem.out)

    • 时空限制:1000ms/256MB

    • 题面:王队在做题,他想把最新的前20道提交了没有$AC$过的题目列出来。如果没有20道,就只输出全部。输入会有如下几个操作:

      • 1 x:王队提交了题号为$x$的$Accepted$的代码
      • 2 x:王队提交了题号为$x$的$UnAccepted$的代码
      • 3:王队现在想知道最新的前20道没有$AC$的题号
    • 输入格式:第一行为两个整数:$n,m$。接下来的$m$行,每行一个命令。

    • 输出格式:对于每一个3的命令的结果,表示未$AC$的题目。保证每一个3命令时至少有一个未解决的题目。

    • 输入样例:

      10000 12

      2 1

      3

      2 9999

      3

      1 1

      3

      2 1

      3

      2 10000

      3

      2 9999

      3

    • 输出样例:

      1
      9999 1
      9999
      9999
      10000 9999
      9999 10000

    • 数据范围:对于$30$%的数据,有$n\leq10^5$;对于$100$的数据,有$n\leq10^9$,$m\leq10^2$。

    • 分析:应该随便搞吧,$m$很小,所以把重点放在$m$上就可以了,$n$很大,不能用桶。

    • $Code$:(期望:100分)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    struct node{
    int Time,Name;
    bool AC;
    }Q[10005];
    int n,m,type,Task,cnt,time;
    int Test[10005],Testcnt;
    int AC[10005],ACcnt;
    inline void Clear(){
    for (int i=1;i<=ACcnt;i++)
    for (int j=1;j<=cnt;j++)
    if (AC[i]==Q[j].Name)
    Q[j].AC=true;
    return;
    }
    bool cmp(node a,node b){
    return a.Time>b.Time;
    }
    int main(){
    freopen("problem.in","r",stdin);
    freopen("problem.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
    scanf("%d",&type);
    if (type==1){
    scanf("%d",&AC[++ACcnt]);
    continue;
    }
    if (type==2){
    scanf("%d",&Task);
    cnt++;
    Q[cnt].Name=Task;
    Q[cnt].Time=++time;
    Q[cnt].AC=false;
    continue;
    }
    if (type==3){
    int ans=0;
    sort (Q+1,Q+cnt+1,cmp);
    Clear();
    Testcnt=0;
    for (int j=1;j<=cnt;j++){
    if (!Q[j].AC){
    bool flag=false;
    for (int k=1;k<=Testcnt;k++)
    if (Test[k]==Q[j].Name){
    flag=true;
    break;
    }
    if (flag) continue;
    printf ("%d ",Q[j].Name);
    Test[++Testcnt]=Q[j].Name;
    ans++;
    if (ans>=20) break;
    }
    }
    printf("\n");
    }
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
    }
  2. 最优交换(swap.cpp/swap.in/swap.out)

    • 时空限制:1000ms/256MB

    • 题面:王队有一个长度为$n$的正整数。他会对这个正整数进行一系列操作,一次操作可以交换该正整数的两个相邻的数位。然而时间有限,他只被允许进行不超过$k$次这样的操作。王队想知道,操作后得到的数最大是多少。

    • 输入格式:第一行一个整数$T$,表示数据组数。每组数据包含一行2个整数,第一个是王队的正整数,第二个是$k$。

    • 输出格式:对于每组数据,输出一行一个正整数,表示得到的最大数是多少。

    • 输入样例:

      2

      1432 2

      4321 2

    • 输出样例:

      4312

      4321

    • 数据说明:对于20%的数据,有$n\leq10,k\leq3$。对于另外20%的数据,T=1且数据随机生成。对于另外20%的数据,$k\leq30$。对于另外20%的数据,$n\leq18$。对于全部数据,$T\leq1000,n\leq 50,0 \leq k \leq 10^5$。

    • 分析:正解应该是贪心,但是我不知道怎么贪$QAQ$,考试的时候甚至还想到了$dp$?!当然我不会打$dp$,我只打了一个暴力。

    • $Code$:(期望:20分)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    using namespace std;
    int T,k,len;
    string str,Maxstr;
    string Max(string a,string b){
    if (a>b) return a;
    return b;
    }
    void dfs(string str,int deep){
    if (deep>k){
    Maxstr=Max(Maxstr,str);
    return;
    }
    for (int i=0;i<len-1;i++){
    swap(str[i],str[i+1]);
    dfs(str,deep+1);
    swap(str[i],str[i+1]);
    }
    return;
    }
    int main(){
    freopen("swap.in","r",stdin);
    freopen("swap.out","w",stdout);
    scanf("%d",&T);
    while (T--){
    cin >>str;
    scanf("%d",&k);
    len=str.length();
    dfs(str,1);


    cout <<Maxstr<<endl;
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
    }
  3. 矩阵(matrix.cpp/matrix.in/matrix.out)

  • 时空限制:2000ms/256MB

  • 题面:有$n \times m$的矩阵,你从左上角走到右下角,每次只能向下或向右走。每个点有一个重量为$v_{i,j}$的价值为$w_{i,j}$的一个物品,你有一个容量为$S$的背包,经过一个点你可以将此点的物品放入背包,求背包物品的最大价值和。

  • 输入格式:第一行三个数$n,m,S$。下面$n$行,每行$m$个数,第$i+1$行第$j$个数表示$v_{i,j}$。下面$n$行,每行$m$个数,第$i+n+1$行第$j$个数表示$ w_{i,j}$。

  • 输出格式:一个数表示最大值。

  • 输入样例:

    3 4 5

    1 2 1 1

    2 3 1 2

    3 2 2 2

    2 3 4 2

    1 4 5 1

    10 1 2 1

  • 输出样例:

    14

  • 数据范围:30%:$n \times m \leq 50 ,S \leq 100$;60%:$n,m \leq 100,S\leq 200$;100%:$n,m \leq 400,0 \leq v_{i,j},w_{i,j}\leq 1000,S\leq 400$。

  • 分析:这是一道裸的背包问题,原来内存限制是128MB,后来变成256MB了,所以3维的$400 \times 400 \times 400$的$dp$数组是可以开的,时间也从1s到了2s。所以考试里调出来的$dp$应该没有什么问题$QAQ$。

  • $Code$:(期望:100分)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int n,m,S,ans;
struct node{
int v,w;
}G[405][405];
int dp[405][405][405];
int main(){
freopen("matrix.in","r",stdin);
freopen("matrix.out","w",stdout);
scanf("%d%d%d",&n,&m,&S);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
scanf("%d",&G[i][j].v);
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
scanf("%d",&G[i][j].w);
for (int s=0;s<=S;s++){
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
if (G[i][j].v<=s)
dp[i][j][s]=max(max(dp[i-1][j][s-G[i][j].v],dp[i][j-1][s-G[i][j].v])+G[i][j].w,max(dp[i][j-1][s],dp[i-1][j][s]));
else dp[i][j][s]=max(dp[i][j-1][s],dp[i-1][j][s]);
}
}
}

printf ("%d\n",dp[n][m][S]);
fclose(stdin);
fclose(stdout);
return 0;
}
  1. 格点统计(count.cpp/count.in/count.out)

    • 时空限制:1000ms/256MB

    • 题面:求第一象限中,位于反比例函数$xy=k$的下方(含边界)的格点的个数。

    • 输入格式:一个正整数$k$。

    • 输出格式:一个整数,要模998244353。

    • 输入样例:

      1. 3

      2. 4

    • 输出样例:

      1. 5

      2. 8

    • 数据范围:

      数据范围

    • 分析:数论找规律吧….反正我推出这么一个东西:

      1
      2
      3
      4
      5
      6
      7
      8
      for (unsigned long long i=1;i<=Sqrt;i++){
      ans+=k-2*i+1;
      if (ans>Mod) ans=ans%Mod;
      }
      ans++;
      ans*=2;
      ans-=Psum;//x=y的个数
      ans=ans%Mod;

      不过测出来证明是错的$QAQ$

  2. 产品排序(product.cpp/product.in/product.out)

    • 时空限制:1000ms/256MB

    • 题面:你是一个公司的员工,你会按时间顺序受到一些产品的订单,你需要用一个栈来改变这些订单的顺序(每个产品都必须入栈和出栈一次)。按初始顺序,每次可以将一个产品入栈,或将栈顶产品弹至现在的序列末尾。每个产品有一个制作时间$t_i$和单位时间惩罚值$d_i$,总的惩罚值为$\sum^{n}_{i=1}(s_i \times d_i)$,其中$s_i$为第$i$个产品的完成时间,你需要最小化总的惩罚值。

    • 输入格式:第一行一个数$n$,表示产品个数。接下来$n$行,每行两个数表示$t_i,d_i$。

    • 输出格式:一行一个数表示最小的总惩罚值。

    • 输入样例:

      4

      1 4

      3 2

      5 2

      2 1

    • 输出样例:

      40

    • 样例解释:

      样例解释

    • 数据范围:30%:$n \leq 15$;50%:$n \leq 100$;100%:$n \leq 200,t_i,d_i \leq 1000$。

    • 分析:题目是看懂了,但是没有任何思路。。。。最后时间不够连暴力都没打$QAQ$

  3. 电话线铺设(telephone.cpp/telephone.in/telephone.out)

    • 时空限制:2000ms/256MB

    • 题面:一个新的小区建成,该小区有$n$栋房子。由于是新小区,还没有铺设电话线,所以社区负责人联系到了工头王队,希望王队以最小的代价铺设电话线。王队的工作就是用$𝑛−1$条电缆将$𝑛$栋房子连成一个连通块。
      王队拥有$𝑛−2$条“王牌电缆”和一条“李牌电缆”,并且他也知道所有可以铺设电缆的房子对的相关信息,即:房子$𝑢$和房子$𝑣$之间可以铺设“王牌电缆”,需要耗费$𝑤$元;房子$𝑥$和房子$𝑦$之间可以铺设“李牌电缆”,需要耗费$l$元。
      请你帮助王队规划一个费用最小的铺设电缆的方案。

    • 输入格式:第一行三个整数$𝑛,𝑊,𝐿$。其中$𝑊,𝐿$分别表示可以铺设“王牌电缆”和“李牌电缆”的房子对的数目。

      接下来$𝑊$行,每行3个整数$𝑢,𝑣,𝑤$表示一对可以铺设“王牌电缆”的房子。把第$𝑖$行(总第$𝑖+1$行)描述的房子对,称作第$𝑖$对“王牌”房子。相同的房子对不会重复出现,且$𝑢≠𝑣$。

      接下来$𝐿$行,每行3个整数$𝑥,𝑦,𝑙$表示一对可以铺设“李牌电缆”的房子。把第$𝑖$行(总第$𝑖+𝑊+1$行)描述的房子对,称作第$𝑖$对“李牌”房子。相同的房子对不会重复出现,且$𝑢≠𝑣$。

    • 输出格式:输出文件的第一行为一个整数$ans$,表示你给出的方案的费用。
      接下来$𝑛−2$行,每行一个整数$𝑢$,表示在第$𝑢$对“王牌”房子之间铺设“王牌电缆”。
      接下来一行一个整数$𝑣$,表示在第$𝑣$对“李牌”房子之间铺设“李牌电缆”。
      除第一行和最后一行外,输出的所有数都必须在$[1,𝑤]$内,且不能有重复的数。最后一行的数必须在$[1,𝑙]$内。一个合法的输出方案的$𝑛−1$条电缆不能连出环,且要使$n$座房子连通。

    • 输入样例:

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

    • 输出样例:

      22
      1
      1
      8
      4
      3
      1

    • 数据范围:

      数据范围

    • 分析:我打了个裸的$Kruskal$,过了样例,但肯定是错的,所以0分$QAQ$。


我决定洗心革面

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×