10-15 考试记
7点开始考试。
第一题大模拟，先跳过。
第二题，裸的背包啊，价值转到下标，切掉切掉。
死亡
（death.pas/c/cpp）
题目背景
众所不周知的是，酒店之王 xkj 一个经常埋葬死去自己的人
当 TA 再一次从迷失的困境之中走出来的时候，TA 被某锤姓男子告知:“你违纪了”
违纪就意味着精神的死亡，灵魂的无处安放
也许这才是最好的归途...... 题目描述
xkj 的灵魂不断的飘荡,飘荡到了食堂的打饭口,TA 无助的望了一眼,下定决心:先把肚
第 4 页 共 4页
子填饱再说
食堂现在还有 n个食物,每一个食物都有一个美味程度wi,但是同样也存在一个费用
vi,xkj 当然希望吃到美食的美味程度总和最大,但是想必你也知道,TA 的饭卡最近有一
些拮据最多只可以消费 W 元,由于 TA 的灵魂在飘荡的时候忘记了带上脑子(唉,脑子是
一个好东西),所以 TA 找到了还在站级部的 cdy,希望 cdy 帮 TA 计算一下,TA 在饭卡不破
产的情况下,该如何消费使自己吃到食物的美味程度总和最大
输入格式
第一行一个整数 n 表示一共有 n 个食物
接下第 2 行至第 n+1 行每行两个整数 vi,wi 表示该食物的费用以及美味程度
最后一行一个整数 W 表示最多可以消费 W 元
输出格式
一行，表示合法消费情况下的最大美味程度总和
样例输入
4
2 3
1 2
3 4
2 2
5
样例输出
7
样例解释
选择 1,3,4 号物品
温馨提示
这不就是一个裸的 01 背包吗??????
数据范围
保证对于 100%的数据
1<=n<=100 1<=wi<=1000 1<=vi<=10^7 1<=W<=10^9
果真全场切。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int wx=200017;
inline int read(){
int sum=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0';ch=getchar();}
return sum*f;
}
int n,m,tot_w;
int w[wx],v[wx],f[wx*5];
signed main(){
freopen("death.in","r",stdin);
freopen("death.out","w",stdout);
n=read();
for(int i=1;i<=n;i++){
v[i]=read();w[i]=read();
tot_w+=w[i];
}
m=read();
memset(f,0x3f,sizeof f);
f[0]=0;
for(int i=1;i<=n;i++){
for(int j=tot_w;j>=w[i];j--){
f[j]=min(f[j],f[j-w[i]]+v[i]);
}
}
for(int i=tot_w;i>=0;i--){
if(f[i]<=m){
printf("%lld
",i);
return 0;
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
第三题是出题大佬讲过的原题，两个月前的吧。。。
刚开始做的时候没想到是原题，一直在YY传递闭包，后来发现是一道原题，直接贪心完事。
%%% lzxkj给衡二校内互坑赛开了多合一题的先河。
code：
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
const int wx=200017;
inline int read(){
int sum=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){ sum=(sum<<1)+(sum<<3)+ch-'0'; ch=getchar();}
return sum*f;
}
int n,ans,ANS,temp,tot,tmp,minn=2147483642;
int b[wx],sum[wx],w[wx];
struct node{
int v,id;
friend bool operator < (const node& a,const node& b){
return a.v<b.v;
}
}a[wx];
void add(int pos,int k){
for(int i=pos;i<=n;i+=(i&-i)){
sum[i]+=k;
}
}
int query(int x){
int re=0;
for(int i=x;i>=1;i-=(i&-i)){
re+=sum[i];
}
return re;
}
signed main(){
freopen("relive.in","r",stdin);
freopen("relive.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)a[i].v=read(),a[i].id=i,w[i]=a[i].v,minn=min(minn,w[i]);
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)b[a[i].id]=i;
for(int i=1;i<=n;i++){
add(b[i],1);
ans+=(i-query(b[i]));
}
for(int i=1;i<=n;i++){
if(a[i].id==i)continue;
int k=a[i].id;
tot=w[i]; temp=1;
a[i].id=i;
tmp=w[i];
while(k!=i){
temp++;tmp=min(tmp,w[k]);
tot+=w[k];
swap(a[k].id,k);
}
if(tmp==minn)
ANS+=tot+tmp*(temp-2);
else
ANS+=min(minn*(temp+1)+tmp+tot,tot+tmp*(temp-2));
}
for(int i=1;i<=n;i++)printf("%lld ",a[i].v);
puts("");
printf("%lld
%lld
",ans,ANS);
fclose(stdin);
fclose(stdout);
return 0;
}
第一题模拟太难受了，最后丢掉了10分。
90分code：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
inline int read(){
int sum=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){sum=(sum<<1)+(sum<<3)+ch-'0';ch=getchar();}
return sum*f;
}
const int wx=1500017;
char zmj[wx],wtx[wx];
int main(){
freopen("lzxkj.in","r",stdin);
freopen("lzxkj.out","w",stdout);
scanf("%s",zmj);
int len=strlen(zmj);
int tmp1=0,tmp2=0,tmp3=0;
int flag=0;
if(len==1&&zmj[0]=='0'){
printf("0
");return 0;
}
else if(len==2&&zmj[0]=='-'&&zmj[1]=='0'){
printf("0
");return 0;
}
for(int i=0;i<len;i++)if(zmj[i]=='-')flag=1;
if(flag)printf("-");
for(int i=len-1;i>=0; i--)
if(zmj[i]>'0'&&zmj[i]<='9'){
tmp3=i;
break;
}
for(int i=0;i<len;i++)
if(zmj[i]>'0'&&zmj[i]<='9'){
tmp1=i;
break;
}
for(int i=0;i<len;i++)
if(zmj[i]=='.'){
tmp2=i;
break;
}
if(tmp1==tmp3&&tmp1==0){
if(zmj[tmp1]=='0')printf("0
");
else{
printf("%c",zmj[tmp1]);
if(tmp2==0){
printf("E%d
",len-1);
}
else{
printf("E%d
",tmp2-tmp1-1);
}
}
return 0;
}
if(tmp2==0){
if(zmj[0]=='.'){
for(int i=tmp1;i<=tmp3;i++){
printf("%c",zmj[i]);
if(i==tmp1&&tmp1!=tmp3)printf(".");
}
printf("E%d
",tmp2-tmp1);
}
else{
for(int i=tmp1;i<=tmp3;i++){
printf("%c",zmj[i]);
if(i==tmp1&&tmp1!=tmp3)printf(".");
}
printf("E%d
",len-tmp1-1);
}
}
else{
if(tmp2<tmp1){
for(int i=tmp1;i<=tmp3;i++){
printf("%c",zmj[i]);
if(i==tmp1&&tmp1!=tmp3)printf(".");
}
printf("E%d
",tmp2-tmp1);
}
else if(tmp2>=tmp1&&tmp2<=tmp3){
for(int i=tmp1;i<=tmp3;i++){
if(zmj[i]=='.')continue;
printf("%c",zmj[i]);
if(i==tmp1)printf(".");
}
printf("E%d
",tmp2-tmp1-1);
}
else{
for(int i=tmp1;i<=tmp3;i++)
{
if(zmj[i]=='.')continue;
printf("%c",zmj[i]);
if(i==tmp1&&tmp1!=tmp3)printf(".");
}
if(tmp2-tmp1==1)return 0;
printf("E%d
",tmp2-tmp1-1);
}
}
fclose(stdin);
fclose(stdout);
return 0;
}
总结：题简单，T2全场切。
三个AK大佬第一题模拟居然打出来了。。。强强强。
290十分，还可以吧，继续加油。