2017 华东师范计算机系暑期夏令营机考
发布时间
阅读量：
阅读量
题目链接<-请点击
题目
A.不等式
B. 1 的个数最多的整数
C. 打印
D. 十亿分考
E. 有钱人买钻石
F. 送分题
A.不等式
将不等式的边界值存起来，然后依次进行判断即可。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200 + 10;
typedef long long LL;
int a[maxn], b[maxn];
string op[maxn];
int main()
{
int n;
scanf("%d",&n);
string x;
for(int i = 1; i <= n; i++)
{
cin >> x;
cin >> op[i];
scanf("%d", &a[i]);
//cout << x << op[i] << a[i] << endl;
if(op[i] == "<") b[i] = a[i] - 1;
else if(op[i] == ">") b[i] = a[i] + 1;
else b[i] = a[i];
}
int ans = 0;
for(int i = 1; i <= n; i++)
{
int res = 0;
for(int j = 1; j <= n; j++)
{
if(op[j] == "=" && b[i] == a[j]) res ++;
else if(op[j] == "<" && b[i] < a[j]) res ++;
else if(op[j] == ">" && b[i] > a[j]) res ++;
else if(op[j] == "<=" && b[i] <= a[j]) res++;
else if(op[j] == ">=" && b[i] >= a[j]) res++;
}
ans = max(ans, res);
}
printf("%d\n",ans);
return 0;
}B. 1 的个数最多的整数
首先将a,b 都化为二进制形式，然后对于a的二进制形式从低位向高位进行遍历，如果该位为0则考虑变为1后是否会大于b，不会大于b则将其变为1后继续判断，否则停止遍历。原理：如果高位可变为1则低位更加能变成1。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 10;
typedef long long LL;
LL a,b;
string change(LL x)
{
string res;
while(x)
{
res += (x%2) + '0';
x >>= 1;
}
return res;
}
int main()
{
int cas = 0,T;
scanf("%d",&T);
while(T--)
{
scanf("%lld%lld",&a,&b);
string sa,sb;
sa = change(a);
sb = change(b);
// cout << sa << endl;
// cout << sb << endl;
LL tmp = 1;
for(int i = 0; i < sb.size(); i++, tmp <<= 1)
if((i >= sa.size() || sa[i] == '0') && a + tmp <= b)
a += tmp;
printf("Case %d: %lld\n",++cas,a);
}
return 0;
}C. 打印
线性DP, 通过插入、删除、复制三个操作进行状态转移。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e7 + 10;
typedef long long LL;
LL dp[maxn];
int main()
{
int n,x,y;
scanf("%d%d%d", &n, &x, &y);
for(int i = 1; i <= n; i++)
if(i % 2 == 0)
dp[i] = min(dp[i-1] + x, dp[i/2] + y);
else dp[i] = min(dp[i-1] + x, min(dp[(i-1)/2]+y+x, dp[(i+1)/2]+y+x));
printf("%lld\n",dp[n]);
return 0;
}D. 十亿分考
直接暴力化分数会WA或者TLE, 考虑通过连分数来进行，小数化连分数、连分数再化分数。
连分数讲解<-请点击
#include <bits/stdc++.h>
using namespace std;
const int maxn = 200 + 10;
typedef long long LL;
double n;
vector<int>cnt;
LL gcd(LL a, LL b)
{
return b == 0? a: gcd(b, a%b);
}
double cal()
{
double res = 0;
for(int i = cnt.size()-1; i >= 0; i--)
{
res += cnt[i];
res = 1/res;
}
return res;
}
int main()
{
double x;
cin >> n;
x = n;
double y = 0;
while(fabs(n-cal()) > 0.5*1e-15)
{
x = 1/x;
cnt.push_back(int(x));
x -= int(x);
}
// for(int i = 0; i < cnt.size(); i++)
// cout << cnt[i] << endl;
LL p = 0,q = 1;
for(int i = cnt.size()-1; i >= 0; i--)
{
p += q*cnt[i];
swap(p,q);
}
// cout << p << q << endl;
LL g = gcd(p,q);
printf("%lld %lld\n",p/g, q/g);
// printf("%.15f\n",1.0*p/q);
return 0;
}E. 有钱人买钻石
使用DFS加贪心，DFS的每一层为一种硬币，因为要总重量（数量）最大，所以从小面额到大面额DFS。DFS从上一层转移到下一层时，使用的本层硬币数为[low,high], high = min(所需要的, 所有的)的数量，low = max(0,high - 5); high 很容易理解，很合理，而low为什么取high-25 ? 最大面额为25， 当前面的某一个面额装换成后面的面额时，最多消耗25个小面额即可。
（如果前面懂了，后面可以不用看了）可以分两个情况来思考一下，一个是如果high = 所有的，说明当前面额不足，所以可以让后面的来补缺口，这个缺口一定视为x+y*大面额，0<=x<=25。如果high = 所需要的，说明当前充足，按理说可以取了所需要的到下一步， 但是可能会出现这样一种情况，当前剩余25，现在面额为10的有三张，为25的有一张，先考虑面额为10的，如果取了两张20的就会导致Impossible。
#include<bits/stdc++.h>
using namespace std;
int p, v[4], c[4] = {1 ,5, 10, 25};
int ans = -1;
bool dfs(int id, int num, int sum)
{
// printf("%d %d %d\n",id, num, sum);
if(sum == p) {ans = num; return true;}
if(id >= 4 || sum > p) return false;
int high = min((p-sum)/c[id], v[id]);
int low = max(0,high-25);
for(int i = high; i >= low; i--)
if(dfs(id+1, num + i, sum + i * c[id])) return true;
return false;
}
int main()
{
scanf("%d%d%d%d%d",&p, &v[0], &v[1], &v[2], &v[3]);
if(dfs(0,0,0)) printf("%d\n", ans);
else printf("Impossible\n");
return 0;
}F. 送分题
离线查询，使用莫队算法可解。莫队算法讲解 <-请点击
因为数据范围为5e5, 使用莫队nsqrt(n) 差不多刚好，和bzoj 1878 HH的项链 大同小异。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;
int n,m,block;
int a[maxn],b[maxn],l[maxn],r[maxn],num[maxn],ans[maxn];
int cl = 1,cr=0,cnt = 0;
map<int,int>mp;
bool cmp(int x, int y)
{
return (l[x]/block) ^ (l[y]/block) ? l[x] < l[y] : r[x] < r[y];
}
void add(int x)
{
if(num[a[x]] == 2) cnt--;
if(++num[a[x]] == 2) cnt++;
}
void del(int x)
{
if(num[a[x]] == 2) cnt--;
if(--num[a[x]] == 2) cnt++;
}
int main()
{
scanf("%d%d",&n, &m);
block = sqrt(n);
int tot = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d",&a[i]);
if(mp.count(a[i]) == 0) mp[a[i]] = tot++;
a[i] = mp[a[i]];
}
memset(num,0,sizeof(num));
// for(int i = 1; i <= n; i++) printf("%d ",a[i]);
// printf("\n");
for(int i = 0; i < m; i++) {scanf("%d%d",&l[i],&r[i]);b[i] = i;}
sort(b,b+m,cmp);
for(int i = 0; i < m; i++)
{
while(cl < l[b[i]]) del(cl++);
while(cl > l[b[i]]) add(--cl);
while(cr < r[b[i]]) add(++cr);
while(cr > r[b[i]]) del(cr--);
// printf("\n");
// printf("%d %d %d %d\n",l[b[i]],r[b[i]],cl,cr);
// for(int j = 0; j < tot; j++) printf("%d ",num[j]);
// printf("\n");
ans[b[i]] = cnt;
}
for(int i = 0; i < m; i++) printf("%d\n",ans[i]);
return 0;
}全部评论 (0)
还没有任何评论哟~