华东师范大学 2017 计算机系暑期夏令营机试
发布时间
阅读量：
阅读量
第一题：https://acm.ecnu.edu.cn/problem/3302/
3302. 打印
题面
统计数据
讨论
单点时限: 2.0 sec
内存限制: 256 MB
印 n 个相同的字符，插入或删除一个字符花费的时间为 x，复制当前整个文本并且粘贴在后面的时间花费为 y，
求完成 n 个字符的打印所需的最小花费时间。输入格式
三个整数 n,x,y (1≤n≤107,1≤x,y≤109)，整数之间用一个空格分隔。对于不超过 30% 的数据，n≤105。
输出格式
输出一个整数表示答案。样例
Input
8 1 1Output
4Input
8 1 10Output
8解题思路
dp
用数组dp[i]来记录打印 i 个相同字符所需的最小花费时间：
对于字数 i 个相同字符;
* 由i-1个字符输入1个字符产生;
* 由（i-1）/2 个字符复制粘贴而成+输入1个字符；
* 由（i-1）/2 个字符复制粘贴而成+删除1个字符；
取三者的最小值
对于偶数 i 个相同字符：
* 由i-1个字符插入一个字符产生；
* 由i/2 个字符复制粘贴而成。
取二者的最小值
AC 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e7+1;
LL dp[maxn];
LL min3(LL a,LL b,LL c){
return (a<b?a:b)<c?(a<b?a:b):c;
}
LL sol(int n,int x,int y)
{
if (n==0) return 0;
if (n==1) return x;
dp[1]=x;
for (int i = 2; i <= n; ++i)
{
if (i%2==1) //奇数
dp[i]=min3(dp[i-1]+x,dp[(i-1)/2]+y+x,dp[(i+1)/2]+y+x);
else //偶数
dp[i]=min(dp[i-1]+x, dp[i/2]+y);
}
return dp[n];
}
int main()
{
int n,x,y;
cin>>n>>x>>y;
LL ans=sol(n,x,y);
cout<<ans<<endl;
return 0;
}
第二题：https://acm.ecnu.edu.cn/problem/3303/；第[;]章第[;]节第[;]小节第[;]条；问题编号为[\texttt{NOI}2,\texttt{P}2,\texttt{T}2,\texttt{S}2]; 题目描述；相关数据统计信息；一相关的讨论区数量
单点时限: 2.0 sec
内存限制: 256 MB
给定整数 a 和 b，输出区间 [a,b] 中对应二进制表示含 1 的个数最多的整数。
如果存在多个解，则输出符合条件的最小的整数。输入格式
第一行一个整数 T (1≤T≤104)，表示问题数。
接下来 T 行，每行两个整数 a,b (0≤a≤b≤263−1)。数据之间用一个空格分隔。
共有两组数据，分别为小数据和大数据，大数据范围如上。对于小数据：T≤10,a≤b≤5⋅106。输出格式
对于每个问题，输出一行 Case x: y，其中 x 是问题编号，从 1 开始，y 是答案。样例
Input
3
0 14
100 1000
3966869755091699093 4597827455649079876Output
Case 1: 7
Case 2: 511
Case 3: 4035225266123964415提示
第一个样例数据：a=0,b=14，在 [0,14] 之间含 1 最多的整数为 7(0111),11(1011),13(1101),14(1110)，输出最小的整数为 7。
注意，第三组样例不会出现在小数据中。解题思路:
数据量很大，注意开unsigned long long。
思路就是在a的基础上不断把低位0变为1（利用巧妙的位运算实现），但不能超出b。
这样同时保证了1的个数最多且数值最小。
可以直接使用
while ( (ans|(ans+1)) <= b )
ans |= (ans+1);
或者使用bitsetAC 代码:
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<bitset>
using namespace std;
typedef unsigned long long uLL;
int NumberOf1(unsigned long long n){
int sum=0;
unsigned long long flag=1;
while(flag){
if(n&flag)
sum++;
flag=flag<<1;
}
return sum;
}
uLL adding_solve(uLL a, uLL b)
{
uLL ans = a;
while((ans|(ans+1))<= b) //从低到高，尝试让低位0变成1
ans|=(ans+1);
return ans;
}
uLL bitset_solve(uLL a, uLL b)
{
uLL weight[64];
weight[0] = 1;
for (int i= 1;i< 64;i++)
weight[i] = weight[i-1]<<1;
bitset<64> bits(a);
uLL ans=a;
for(int i=0;i< 64;i++)
{
if(bits[i]==0)
{
ans+=weight[i]; //尝试让低位0变成1
if (ans>b)
{
ans-=weight[i];
break;
}
}
}
return ans;
}
int main()
{
int T;
scanf("%d",&T);
for(int tt=1;tt<=T;tt++)
{
uLL a, b;
scanf("%llu%llu",&a,&b);
uLL ans = bitset_solve(a, b);
printf("Case %d: %llu\n",tt,ans);
}
return 0;
}
第三题： https://acm.ecnu.edu.cn/problem/3304/
单点时限: 2.0 sec
内存限制: 256 MB
给定 n 个关于整数 X 的不等式，问最多有多少个不等式成立。
每个不等式为如下的形式之一：
X < C
X <= C
X = C
X > C
X >= C输入格式
第一行一个整数 n (1≤n≤200)，表示不等式个数。
接下来 n 行，每行一个不等式。
不等式输入格式为：X sign C，关系运算符 (sign) 左右各有一个空格，C 是整数，0≤C≤109。
关系运算符为：<, <=, =, >, >=。
对于 35% 的数据，关系运算符只会出现 <= 和 >=。
对于 85% 的数据，C≤103。
输出格式
输出最多可以同时成立的不等式个数。
样例
Input
4
X = 1
X = 2
X = 3
X > 0Output
2Input
10
X >= 10
X <= 90
X = 1
X > 35
X < 90
X <= 1000
X > 0
X = 900
X < 500
X > 300
Output
7Input
3
X > 10
X < 10
X = 10Output
1解题思路：
对输入数据进行初步处理后，在三个预设区间内进行分类统计。具体操作如下：将高于等于设定临界值的数据点归入ae[]数组；将低于等于设定临界值的数据点归入be[]数组；最后将正好等于设定临界值的数据点单独统计为ee[]数组。
由于数据量较小，在题解之后采用暴力枚举的方法即可解决这类问题
注意：我使用了gets(),提交时选择C++11
AC 代码
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<bitset>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=205;
int main(){
int T;
scanf("%d\n",&T);
int ae[maxn],be[maxn],ee[maxn];
int ans=0,aecnt=0,becnt=0,eecnt=0;
//int low=1000000005,hi;
while(T--){
char str[20],cc[5],xx;
int a,b;
gets(str);
//puts(str);
sscanf(str,"%c %s %d",&xx,&cc,&a);
// printf("%s %d\n",cc,a);
if(strcmp(cc,"<")==0){
be[becnt]=a-1;becnt++;
}
if(strcmp(cc,"<=")==0){
be[becnt]=a;becnt++;
}
if(strcmp(cc,"=")==0){
ee[eecnt]=a;eecnt++;
}
if(strcmp(cc,">")==0){
ae[aecnt]=a+1;aecnt++;
}
if(strcmp(cc,">=")==0){
ae[aecnt]=a;aecnt++;
}
//printf("%d %d %d\n",aecnt,eecnt,becnt);
}
sort(ae,ae+aecnt);
sort(ee,ee+eecnt);
sort(be,be+becnt);
//按照=
for(int i=0;i<eecnt;i++){
int jgee=0;
int ii,jj,kk=0;
for(ii=0;ii<aecnt;ii++){
if(ae[ii]>ee[i]){
break;
}
}
jgee+=ii;//printf("ae %d ",ii);
for(jj=becnt-1;jj>=0;jj--){
if(be[jj]<ee[i]){
break;
}
}
jgee+=(becnt-1-jj);//printf("be %d ",jj);
for(int ziji=0;ziji<eecnt;ziji++){
if(ee[ziji]==ee[i]) kk++;
}
jgee+=kk;//printf("be %d ",kk);
// printf("\n-----------------\n");
if(jgee>ans) ans=jgee;
}
//按照》=
for(int i=0;i<aecnt;i++){
int jgae=i+1,ii;
for(ii=becnt-1;ii>=0;ii--){
if(be[ii]<ae[i]){
break;
}
}
jgae+=becnt-1-ii;
if(jgae>ans) ans=jgae;
}
//按照 《=
for(int i=0;i<becnt;i++){
int jgbe=becnt-i,ii;
for(ii=0;ii<aecnt;ii++){
if(ae[ii]>be[i]){
break;
}
}
jgbe+=ii;
if(jgbe>ans) ans=jgbe;
}
printf("%d\n",ans);
return 0;
}
全部评论 (0)
还没有任何评论哟~