第一题：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/ 3303. 1 的个数最多的整数 题面 统计数据 1 个讨论
单点时限: 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 > 300Output
7Input
3 X > 10 X < 10 X = 10Output
1解题思路： 解题思路： 处理一下输入，临界值分别放入三个数组 ae[] above equal >= be[] below equal <= ee[] equal equal =
数据量比较小，题后暴力枚举即可 （1）从ae[]考虑，只需考虑be[]数组，不需要考虑ae中重复的临界值，因为会覆盖掉； （2）从be[]考虑，只需考虑ae[]数组，不需要考虑be中重复的临界值，因为会覆盖掉； （3）从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; }