2019.4.6高中部集训 - Snowflake

考试

上午

刷题计划（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分）

#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;
}

最优交换（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分）

#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;
}

矩阵（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

输出样例：

数据范围：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分）

#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; }

格点统计（count.cpp/count.in/count.out）

时空限制：1000ms/256MB
题面：求第一象限中，位于反比例函数$xy=k$的下方（含边界）的格点的个数。
输入格式：一个正整数$k$。
输出格式：一个整数，要模998244353。
输入样例：
1. 3
2. 4
输出样例：
1. 5
2. 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$

产品排序（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$

电话线铺设（telephone.cpp/telephone.in/telephone.out）

时空限制：2000ms/256MB
题面：一个新的小区建成，该小区有$n$栋房子。由于是新小区，还没有铺设电话线，所以社区负责人联系到了工头王队，希望王队以最小的代价铺设电话线。王队的工作就是用$

本文作者：Snowflake_Pink
本文链接：https://snowflake.pink/archives/24/
最后修改时间：2020-04-13 11:15:29
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！

留下你成为大佬的想法吧

支持 Markdown 语法

课程表

上午

下午

晚上

考试

上午