试题
编号：
201412-1试题
名称：
门禁系统时间
限制：
1.0s内存 限制：256.0MB问题
描述：
问题描述
涛涛最近要负责图书馆的管理工作，需要记录下每天读者的到访情况。每位读者有一个编号，每条记录用读者的编号来表示。给出读者的来访记录，请问每一条记录中的读者是第几次出现。
输入格式
输入的第一行包含一个整数n，表示涛涛的记录条数。 第二行包含n个整数，依次表示涛涛的记录中每位读者的编号。
输出格式
输出一行，包含n个整数，由空格分隔，依次表示每条记录中的读者编号是第几次出现。
样例输入
5 1 2 1 1 3
样例输出
1 1 2 3 1
评测用例规模与约定
1≤n≤1,000，读者的编号为不超过n的正整数。
分析：简单题，先用桶记录各个数出现次数，遇到桶中有数就输出从1开始
#include<iostream> using namespace std; int main() { int n; cin>>n; int *array; array=new int[n]; for(int i=0;i<n;i++) cin>>array[i]; for(int i=0;i<n;i++) { int number=1; for(int j=0;j<i;j++) { if(array[i]==array[j]) number++; } cout<<number<<" "; } return 0; }
试题
编号：
201412-2试题
名称：
Z字形扫描时间
限制：
2.0s内存
限制：
256.0MB问题描述：问题描述
在图像编码的算法中，需要将一个给定的方形矩阵进行Z字形扫描(Zigzag Scan)。给定一个n×n的矩阵，Z字形扫描的过程如下图所示： 对于下面的4×4的矩阵， 1 5 3 9 3 7 5 6 9 4 6 4 7 3 1 3 对其进行Z字形扫描后得到长度为16的序列： 1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3 请实现一个Z字形扫描的程序，给定一个n×n的矩阵，输出对这个矩阵进行Z字形扫描的结果。
输入格式
输入的第一行包含一个整数n，表示矩阵的大小。 输入的第二行到第n+1行每行包含n个正整数，由空格分隔，表示给定的矩阵。
输出格式
输出一行，包含n×n个整数，由空格分隔，表示输入的矩阵经过Z字形扫描后的结果。
样例输入
4 1 5 3 9 3 7 5 6 9 4 6 4 7 3 1 3
样例输出
1 5 3 9 7 3 9 5 4 7 3 6 6 4 1 3
评测用例规模与约定
1≤n≤500，矩阵元素为不超过1000的正整数。
分析：首先不难看出是一种斜线输出，奇数次从左下到右上，偶数次则从右上到左下，问题的关键是找出起始点的坐标，然后每次横坐标和纵坐标都加一或减一（看奇数或偶数），以第n次输出为分界线，第n次输出后的情况再讨论
#include <iostream> using namespace std; const int N = 500; int a[N][N]; int main() { int n, x, y; // 输入数据 cin >> n; for(int i=0; i<n; i++) for(int j=0; j<n; j++) cin >> a[i][j]; // 输出左上三角 x = 0; y = 0; for(int i=0; i<n; i++) if(i & 1) { for(int j=0; j<i; j++) cout << a[x++][y--] << " "; cout << a[x++][y] << " "; } else { for(int j=0; j<i; j++) cout << a[x--][y++] << " "; cout<< a[x][y++] << " "; } // 输出右下三角 if(n & 1) y--, x++; else y++, x--; for(int i=n-2; i>0; i--) if(i & 1) { for(int j=0; j<i; j++) cout << a[x++][y--] << " "; cout << a[x][y++] << " "; } else { for(int j=0; j<i; j++) cout << a[x--][y++] << " "; cout << a[x++][y] << " "; } if(n!=1) cout << a[n-1][n-1] << endl; return 0; }试题
编号：
201412-3试题
名称：
集合竞价时间
限制：
1.0s内存
限制：
256.0MB问题
描述：
问题描述
某股票交易所请你编写一个程序，根据开盘前客户提交的订单来确定某特定股票的开盘价和开盘成交量。 该程序的输入由很多行构成，每一行为一条记录，记录可能有以下几种： 1. buy p s 表示一个购买股票的买单，每手出价为p，购买股数为s。 2. sell p s 表示一个出售股票的卖单，每手出价为p，出售股数为s。 3. cancel i表示撤销第i行的记录。 如果开盘价为p0，则系统可以将所有出价至少为p0的买单和所有出价至多为p0的卖单进行匹配。因此，此时的开盘成交量为出价至少为p0的买单的总股数和所有出价至多为p0的卖单的总股数之间的较小值。 你的程序需要确定一个开盘价，使得开盘成交量尽可能地大。如果有多个符合条件的开盘价，你的程序应当输出最高的那一个。
输入格式
输入数据有任意多行，每一行是一条记录。保证输入合法。股数为不超过108的正整数，出价为精确到恰好小数点后两位的正实数，且不超过10000.00。
输出格式
你需要输出一行，包含两个数，以一个空格分隔。第一个数是开盘价，第二个是此开盘价下的成交量。开盘价需要精确到小数点后恰好两位。
样例输入
buy 9.25 100 buy 8.88 175 sell 9.00 1000 buy 9.00 400 sell 8.92 400 cancel 1 buy 100.00 50
样例输出
9.00 450
评测用例规模与约定
对于100%的数据，输入的行数不超过5000。
分析：一题较为恶心的大模拟，需要用到stl set、前缀和等知识，首先直观感知开盘价一定是在买单这里，具体证明
证明：1. 如果开盘价即在买家中，又在卖家中，那开盘价已经是买家价格之一了。
2. 如果开盘价p1只在卖家中，没有在买家中，那么在买家中找到与p1价格相差最小却又比p1大的价格p2。（若找不到p2，p1比买家中的任意价格都要大，此时成交价格为0，无意义，不考虑这种情况）当开盘价为p2时，买家中的总销量与开盘价为p1时相等，卖家中的总销量大于或者等于开盘价为p1时的总销量（因为p2大于p1，且距离p1最近，所以对于买家中的总销量是没有影响的，对于卖家中的总销量，如果卖家中存在大于p1小于p2的价格时，总销量还会增大，否则不变）。所以当开盘价为p2时，成交量要么与p1时相等，要么比p1时大。由于题目中说了，如果有多个符合条件的开盘价，应输出最大的价格，所以此时开盘价应选为p2，即开盘价不可能只在卖家中。
3.如果开盘价p1既不在买家中又不在卖家中，同理在买家中找到与p1相差最小价格大于p1的价格p2。同样可证明p2应为开盘价，证明方式同2。
具体实现：开两个set，一个存buy，一个存sell，当然需要把每次输入的字符串存一下遇到cancel指令去找对应的第x条指令是buy还是sell（这里不考虑cancel一条cancel指令，因为根据题意没有意义）然后去对应的set去找，
注意，buy中的出价一定要从高到低，sell中的卖价一定是从低到高，两个前缀和分别记录它们的和，为什么？
为什么？因为根据我们的结论，你是去枚举买单里的每一个出价，当你枚举到一个出价时，出价至少为p0的买单的总股数不就是其对应的前缀和吗？同理所有出价至多为p0的卖单的总股数也是这样，这样方便处理
之后就是不断遍历不断更新答案了，最后再扫一遍找出那个开盘价是啥就完了
上一波AC代码~
#include<bits/stdc++.h> #define rg register long long #define inf 2147483647 #define min(a,b) (a<b?a:b) #define max(a,b) (a>b?a:b) #define ll long long #define maxn 5005 #define endl "\n" #define N 6000 const double eps=1e-8; using namespace std; inline ll read() { char ch=getchar();ll s=0,w=1; while(ch<48||ch>57){if(ch=='-')w=-1;ch=getchar();} while(ch>=48&&ch<=57){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();} return s*w; } inline void write(ll x) { if(x<0)putchar('-'),x=-x; if(x>9)write(x/10); putchar(x+48); } struct node { double price; ll stock; ll num; inline bool operator <(const node &s) const { return price<s.price; } }; struct node1 { double price; ll stock; ll num; inline bool operator <(const node1 &s) const { return price>s.price; } }; string s[maxn]; ll tot=0,ans; multiset<node>sell;//从小到大 multiset<node1>buy;//从大到小 ll sum1[maxn],sum2[maxn]; int main() { while(1) { cin>>s[++tot]; if(s[tot]=="buy") { node1 temp; temp.num=tot; cin>>temp.price>>temp.stock; buy.insert(temp); } else if(s[tot]=="sell") { node temp; temp.num=tot; cin>>temp.price>>temp.stock; sell.insert(temp); } else if(s[tot]=="cancel") { ll x=read(); if(s[x]=="sell") { for(auto it=sell.begin();it!=sell.end();it++) { if((*it).num==x) { //cout<<sell.size()<<endl; sell.erase(it); // cout<<sell.size()<<endl; break; } } } else if(s[x]=="buy") { for(auto it=buy.begin();it!=buy.end();it++) { if((*it).num==x) { buy.erase(it); // cout<<1<<endl; break; } } } } else { /* for(auto it=sell.begin();it!=sell.end();it++) { cout<<(*it).price<<" "<<(*it).stock<<endl; } for(auto it=buy.begin();it!=buy.end();it++) { cout<<(*it).price<<" "<<(*it).stock<<endl; }*/ ll cnt=0; for(auto it=buy.begin();it!=buy.end();it++) { cnt++; sum1[cnt]=sum1[cnt-1]+(*it).stock; //cout<<sum1[cnt]<<endl; } cnt=0; for(auto it=sell.begin();it!=sell.end();it++) { cnt++; sum2[cnt]=sum2[cnt-1]+(*it).stock; // cout<<sum2[cnt]<<endl; } cnt=0; ll ans=-1; for(auto it=buy.begin();it!=buy.end();it++) { cnt++; ll cmp1=sum1[cnt],cmp2=0,tempans,cnt1=0; for(auto it1=sell.begin();it1!=sell.end();it1++) { if((*it).price<(*it1).price) { break; // cout<<cmp1<<" "<<cmp2<<endl; } cnt1++; cmp2=sum2[cnt1]; //cout<<cnt<<" "<<cmp1<<" "<<cmp2<<endl; tempans=min(cmp1,cmp2); ans=max(ans,tempans); } } cnt=0; for(auto it=buy.begin();it!=buy.end();it++) { cnt++; ll cmp1=sum1[cnt],cmp2=0,tempans,cnt1=0; for(auto it1=sell.begin();it1!=sell.end();it1++) { if((*it).price<(*it1).price) { break; // cout<<cmp1<<" "<<cmp2<<endl; } cnt1++; cmp2=sum2[cnt1]; //cout<<cnt<<" "<<cmp1<<" "<<cmp2<<endl; tempans=min(cmp1,cmp2); if(tempans==ans) { cout<<setiosflags(ios::fixed)<<setprecision(2)<<(*it).price<<" "; cout<<ans<<endl; return 0; } } } //cout<<ans<<endl; return 0; } } return 0; } 试题 编号：201412-4试题 名称：最优灌溉时间 限制：1.0s内存
限制：
256.0MB问题 描述：
问题描述
雷雷承包了很多片麦田，为了灌溉这些麦田，雷雷在第一个麦田挖了一口很深的水井，所有的麦田都从这口井来引水灌溉。 为了灌溉，雷雷需要建立一些水渠，以连接水井和麦田，雷雷也可以利用部分麦田作为“中转站”，利用水渠连接不同的麦田，这样只要一片麦田能被灌溉，则与其连接的麦田也能被灌溉。 现在雷雷知道哪些麦田之间可以建设水渠和建设每个水渠所需要的费用（注意不是所有麦田之间都可以建立水渠）。请问灌溉所有麦田最少需要多少费用来修建水渠。
输入格式
输入的第一行包含两个正整数n, m，分别表示麦田的片数和雷雷可以建立的水渠的数量。麦田使用1, 2, 3, ……依次标号。 接下来m行，每行包含三个整数ai, bi, ci，表示第ai片麦田与第bi片麦田之间可以建立一条水渠，所需要的费用为ci。
输出格式
输出一行，包含一个整数，表示灌溉所有麦田所需要的最小费用。
样例输入
4 4 1 2 1 2 3 4 2 4 2 3 4 3
样例输出
6
样例说明
建立以下三条水渠：麦田1与麦田2、麦田2与麦田4、麦田4与麦田3。
评测用例规模与约定
前20%的评测用例满足：n≤5。 前40%的评测用例满足：n≤20。 前60%的评测用例满足：n≤100。 所有评测用例都满足：1≤n≤1000，1≤m≤100,000，1≤ci≤10,000。
分析：做完第三题大模拟，看到这个蒙了，不就是mst的板子题吗？？？？？其实应该用prim的，因为是稀疏图，kruskal可能时间会比较久，但是就是莽着一交46ms吧
#include<bits/stdc++.h> using namespace std; #define re register #define il inline il int read() { re int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();} while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar(); return x*f; }//快读，不理解的同学用cin代替即可 #define inf 123456789 #define maxn 5005 #define maxm 200005 struct edge { int v,w,next; }e[maxm<<1]; //注意是无向图，开两倍数组 int head[maxn],dis[maxn],cnt,n,m,tot,now=1,ans; //已经加入最小生成树的的点到没有加入的点的最短距离，比如说1和2号节点已经加入了最小生成树，那么dis[3]就等于min(1->3,2->3) bool vis[maxn]; //链式前向星加边 il void add(int u,int v,int w) { e[++cnt].v=v; e[cnt].w=w; e[cnt].next=head[u]; head[u]=cnt; } //读入数据 il void init() { n=read(),m=read(); for(re int i=1,u,v,w;i<=m;++i) { u=read(),v=read(),w=read(); add(u,v,w),add(v,u,w); } } il int prim() { //先把dis数组附为极大值 for(re int i=2;i<=n;++i) { dis[i]=inf; } //这里要注意重边，所以要用到min for(re int i=head[1];i;i=e[i].next) { dis[e[i].v]=min(dis[e[i].v],e[i].w); } while(++tot<n)//最小生成树边数等于点数-1 { re int minn=inf;//把minn置为极大值 vis[now]=1;//标记点已经走过 //枚举每一个没有使用的点 //找出最小值作为新边 //注意这里不是枚举now点的所有连边，而是1~n for(re int i=1;i<=n;++i) { if(!vis[i]&&minn>dis[i]) { minn=dis[i]; now=i; } } ans+=minn; //枚举now的所有连边，更新dis数组 for(re int i=head[now];i;i=e[i].next) { re int v=e[i].v; if(dis[v]>e[i].w&&!vis[v]) { dis[v]=e[i].w; } } } return ans; } int main() { init(); printf("%d",prim()); return 0; }第五题暂缺，网络流还没看...
