ACM训练日记—4月21日（西安电子科技大学第16届程序设计竞赛网络同步赛）

本文主要是介绍ACM训练日记—4月21日（西安电子科技大学第16届程序设计竞赛网络同步赛），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

整理下题目。

前三个题超水，就不整理了。

D—另一个另一个简单游戏

题目：现在有n个数，每次随机取出两个数x,y，然后加入一个数为(x+y)/2，问最后剩下的那个数的期望是多少？

可以看到每次去掉两个数，加入其中位数，那么操作n-1次后剩下的数相当于平均数，写写样例就能发现

代码：

ll a[105];
int main()
{
ll n,k;
int T;
scanf("%d",&T);
while(T--)
{
ll ans=0;
scanf("%lld",&n);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
ans+=a[i];
}
ans=ans/n;
cout<<ans<<endl;
}
}

F—Operating System

题目：现在有一个大小为可以容纳N个页面的内存，硬盘内的内容被分成M个页面，用1~M来标识，一开始内存里没有任何页面，接下来用户会请求Q个页面，你需要设计一个置换算法，使得缺页发生的次数最少。缺页是指用户请求某个编号的页面，但这个页面没有在内存中的情况。发生缺页之后，你必须要把硬盘内对应的页面调入内存中，如果内存已满，你需要置换掉当前内存中的某个页面。

这个题其实就是贪心+模拟

先处理出序列每一位数下一次出现在哪个位置，没在出现的赋值-1，然后找一个优先队列（从小到大排），遍历数列，如果第i位上的数在队列里就continue，如果不在就取出优先队列里最小的数。

代码：

int n,m,q;
int a[50005];
int mp[50005];
int vis[50005];
int main()
{
priority_queue<int>h;
while(scanf("%d%d%d",&n,&m,&q)!=EOF)
{
while(!h.empty()) h.pop();
memset(vis,-1,sizeof(vis));
memset(mp,0,sizeof(mp));//记录该位上的值下次出现的位置
for(int i=1;i<=q;i++)
{
scanf("%lld",&a[i]);
if(mp[a[i]]==0)
{
mp[a[i]]=i;
}
else
{
int t=a[i];
vis[mp[t]]=i;
mp[t]=i;
}
}
//for(int i=1;i<=q;i++) cout<<vis[i]<<" ";cout<<endl;
memset(mp,0,sizeof(mp));
int ans=0;
for(int i=1;i<=q;i++)
{
if(mp[a[i]]) continue;//该值在队列里
if(h.size()<n)//队列不满，继续放
{
h.push(vis[i]);
mp[a[i]]=1;
ans++;
}
else//取出最小的，因为会优先取出-1（后面没在出现的值）
{
ll e=h.top();
h.pop();
h.push(vis[i]);
mp[e]=0;
mp[a[i]]=1;
ans++;
}
}
cout<<ans<<endl;
}
}

E—Xieldy And His Password

为了改变这一现状，他random了一个01串，并从中截取了一段作为自己的口令。

他选择的口令满足以下条件：
1. 口令串表示的二进制数在十进制下可以被表示为3k(k>=0)。
2. 口令串可以有前导零。
现已经random出了01串，他想知道有多少种口令方案可以选择（不同的子段即为不同）。

首先，一个二进制序列后面添上个0，相当于此二进制数乘2。一个二进制序列后面添上个1，相当于此二进制数乘2加1。

那么dp[i][j]表示以i位为结尾的数mod3余j，那么

当a[i]=='0'

dp[i][0]=1//表示以这第i位开头的情况，下面是由前面类推出来的

dp[i][0]+=dp[i-1][0];//mod3=0的数乘2还是可以被3整除
dp[i][1]+=dp[i-1][2];//后面依次类推
dp[i][2]+=dp[i-1][1];

当a[i]=='1'

dp[i][1]=1//表示以i位开头的情况。

dp[i][0]+=dp[i-1][1];
dp[i][1]+=dp[i-1][0];
dp[i][2]+=dp[i-1][2];

这样依次加和dp[i][0]就可以了。

代码：

#define N 1000010
char a[N];
long long dp[N][3];
int main()
{
long long s;
int i,j,k;
while(scanf("%s",a+1)!=EOF)
{
memset(dp,0,sizeof(dp));
k=strlen(a+1);
s=0;
for(i=1;i<=k;i++)
{
if(a[i]=='0')
{
dp[i][0]=1;
dp[i][0]+=dp[i-1][0];
dp[i][1]+=dp[i-1][2];
dp[i][2]+=dp[i-1][1];
}
else
{
dp[i][1] = 1;
dp[i][0]+=dp[i-1][1];
dp[i][1]+=dp[i-1][0];
dp[i][2]+=dp[i-1][2];
}
s=s+dp[i][0];
}
printf("%lld\n",s);
}
return 0;
}

G—小国的复仇

题目：在游戏中他要得到n个小国，初始的时候小国和小杰各有1个。经过了很久的修炼，汀老师学会了两种魔法，他每次可以动用自己的智慧来使用魔法。
第一个魔法：（小杰变小国）可以将自己的智慧复制和当前小杰一样数量的小国出来；
第二个魔法：（小国大爆发）可以将当前的小杰变成和小国的数量一样，然后小国的数量加倍！
因为汀老师的智力是无限多的，他不关心花掉的智力大小。但是好学的汀老师想尽快得到n个小国，使得能有更多的时间去读paper和打比赛。他想问问你，最少需要使用多少次魔法可以得到n个小国。
得到了n个小国后，汀老师去学习，但是小国们基因突变在电脑里越来越多！他们来组织汀老师学习，现在告诉汀老师我要得到更多的同伴！

其实画一下二叉树图就能很容易发现规律，假如给出一个数n，如果n是素数，ans=n-1，如果是合数，就是将n分解为若干素数加和，n=a1+a2+...an(ai是素数)，那么ans=(a1-1)+...(an-1)。

代码：

const int MAXN = 1000010;
int len = 0, prime[MAXN], f[MAXN];
bool notPrime[MAXN];
void makePrime() {
for(int i = 2; i < MAXN; ++ i) {
if(!notPrime[i]) {
prime[++ len] = i;
for(int j = 2; j * i < MAXN; ++ j)
notPrime[j * i] = 1;
}
}
return ;
}
int main() {
makePrime();
int n, i, j, tmp;
for(i = 1; i <= len; ++ i)
f[prime[i]] = prime[i] - 1;
for(i = 4; i < MAXN; ++ i) {
if(notPrime[i]) {
tmp = i;
for(j = 1; j <= len && prime[j] <= tmp; ++ j) {
while(tmp % prime[j] == 0) {
f[i] += f[prime[j]];
tmp /= prime[j];
}
if(f[tmp]) {
f[i] += f[tmp];
tmp = 0;
}
}
if(tmp) f[i] += f[tmp];
}
}
cin >> n;
while(n --) {
scanf("%d", &i);
printf("%d\n", f[i]);
}
return 0;
}