武汉大学新生寒假集训测试Day7 题解

A

Codeforces Round #479 (Div. 3)

题目大意

求出现次数最多的two-gram的子串，一个two-gram串是指在原字符串中出现的连续的两个字母.

思路

直接枚举每每相邻的两个字符，用map或者hash计一下出现次数不断取max即可。

代码

#include< cstdio >
#include< cstring >
#include< algorithm >
#include< map >
#include< iostream >
#include< string >
using namespace std;
const int maxn=200005;
map<string,int> mp;
int maxx=0,n;
char str[maxn];
string ans;
int main()
{
	scanf("%d",&n);
	scanf("%s",str+1);
	for(int i=1;i<n;i++)
	{
		string temp="";
		temp+=str[i];
		temp+=str[i+1];
		mp[temp]++;
		if(mp[temp]>maxx)
		{
			maxx=mp[temp];
			ans=temp;
		}
	}
	cout<<ans;
	return 0;
}

B

Codeforces Round #479 (Div. 3)

题目大意

给出一个n个数字组成的序列，问是否存在一个整数x，使得该序列刚好有k个数小于或等于x，存在即输出该x，否则输出-1。

$(1\leq x,a_i\leq10^9)$

思路

直接从小到大排序，取第k个数即可。如果第k个数和第k+1个数相等，那么就一定不存在整数x，使得恰好有k个数小于或等于x。**这里要特别注意k=0的情况,如果k=0并且最小的数不为1，那么就有解，反之则无解。

代码

#include< cstdio >
#include< cstring >
#include< algorithm >
using namespace std;
const int maxn=200005;
int n,k,a[maxn];
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1);
	if(k)
	{
		if(a[k]==a[k+1]) printf("-1\n");
		else printf("%d\n",a[k]);
	}
	else
	{
		if(a[1]==1) printf("-1\n");
		else printf("1\n");
	}
	return 0;
}

C

Codeforces Round #479 (Div. 3)

题目大意

给出一个数n，求将这个数按以下规则操作k次后的结果是多少。

• 如果这个数最后一位不是0，那么将这个数减去1。
• 如果这个数最后一位是0，那么将这个数除以10。

思路

按题目要求模拟即可。

代码

#include< cstdio >
#include< cstring >
#include< algorithm >
using namespace std;
const int maxn=200005;
int n,k;
int main()
{
	scanf("%d%d",&n,&k);
	while(k--)
	{
		if(n%10!=0) n--;
		else n/=10;
	}
	printf("%d\n",n);
	return 0;
}

D

Codeforces Round #479 (Div. 3)

题目大意

最开始有一个数x，可以将它乘2，或者如果它能整除3，可以将它除以3，再将得到的数这样操作，就会得到一连串的数。现在给出最后得到的一连串的n个数，反推每一次操作时的数。

$1\leq n\leq100\\1\leq a_i\leq3\times10^{18}\;(1\leq i\leq n)\\$

思路

直接dfs搜索……没想到这么水。

代码

#include< cstdio >
#include< cstring >
#include< algorithm >
#include< set >
using namespace std;
const int maxn=200005;
long long n,a[maxn],ans[maxn];
set<long long> s;
void dfs(int x)
{
	if(x==n)
	{
		for(int i=1;i<=n;i++) printf("%lld ",ans[i]);
		exit(0);
	}
	long long temp=ans[x]*2;
	set<long long>::iterator it;
	it=s.find(temp);
	if(it!=s.end())
	{
		s.erase(it);
		ans[x+1]=temp;
		dfs(x+1);
		s.insert(temp);
	}
	if(ans[x]%3!=0) return;
	temp=ans[x]/3;
	it=s.find(temp);
	if(it!=s.end())
	{
		s.erase(it);
		ans[x+1]=temp;
		dfs(x+1);
		s.insert(temp);
	}
}
int main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		s.insert(a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		ans[1]=a[i];
		s.erase(ans[1]);
		dfs(1);
		s.insert(ans[1]);
	}
	return 0;
}

E

Codeforces Round #478 (Div. 2)

题目大意

给出一个字符串，问有几个root,root的意思是一个字符串中所有的不重复字母，无关顺序。

• 比如a,aa,aaa,ab,abb，去重后的是字符串是a,a,a,ab,ab，只有a,ab两个root。
• 比如amer,arem,mrea，只有一个root。

思路

直接枚举所有的字串，因为英文小写字母只有26个，所以在这里我采用了状态压缩，每一个字母对应二进制下的一位。用状压之后的数存map，就保证了与顺序没有关系，然后统计有多少个不同数即可。如果用set的话也可以直接输出set中元素的个数。

代码

#include< cstdio >
#include< cstring >
#include< algorithm >
#include< map >
using namespace std;
const int maxn=200005;
map<int,bool> mp;
int b[maxn],n,ans=0;
char str[maxn];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",str+1);
		int len=strlen(str+1);
		int temp=0;
		for(int j=1;j<=len;j++)
		{
			int p=str[j]-'a';
			temp|=(1<<p);
		}
		if(!mp[temp]) ans++;
		mp[temp]=true;
	}
	printf("%d\n",ans);
	return 0;
}

F

Codeforces Round #478 (Div. 2)

题目大意

你有n个士兵，每个士兵的生命值为ai，有q轮攻击，每轮攻击的伤害值为ki，如果在某一轮中士兵全部死光了，那么在这一轮结束的时候就会全部复活，且这一轮攻击剩下的伤害就会被忽略，问你每轮攻击结束后你会有多少个士兵。

思路

用前缀和统计前n个士兵的生命值。每次攻击时先判断是否可以全部击杀，如果可以，答案为n；如果不能，用二分找到第一个大于等于当前攻击值所对应的编号pos。如果攻击值刚好可以击杀位置为pos的士兵，那么答案就是n-pos，如果还不足以击杀位置为pos的士兵，那么答案就是n-pos+1。

代码

#include< cstdio >
#include< cstring >
#include< algorithm >
using namespace std;
const int maxn=200005;
long long n,q,a[maxn];
int main()
{
	scanf("%lld%lld",&n,&q);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=n;i++) a[i]+=a[i-1];
	long long tot=0;
	while(q--)
	{
		long long x;
		scanf("%lld",&x);
		tot+=x;
		if(tot>=a[n])
		{
			printf("%lld\n",n);
			tot=0;
			continue;
		}
		int pos=lower_bound(a+1,a+n+1,tot)-a;
		if(a[pos]-tot) printf("%lld\n",n-pos+1);
		else printf("%lld\n",n-pos);
	}
	return 0;
}

G

Codeforces Round #478 (Div. 2)

题目大意

有14个洞，可以选择从第i个洞取出全部石头，然后在第i+1上放一个，第i+2上放一个，14个洞不停循环放置，直到全部放完，然后把14个洞里偶数的数相加，求最大值。

思路

模拟，关键要看懂题。每个洞取出来放一放，取最大值即可。

代码

#include< cstdio >
#include< cstring >
#include< algorithm >
using namespace std;
const int maxn=200005;
long long a[maxn],ans=0,b[maxn];
int main()
{
	for(int i=1;i<=14;i++) scanf("%lld",&a[i]);
	for(int i=1;i<=14;i++)
	{
		if(a[i]==0) continue;
		long long x=a[i]/14;
		for(int j=1;j<=14;j++)
		{
			if(i==j) b[j]=x;
			else b[j]=a[j]+x;
		}
		long long res=a[i]%14;
		int now=i+1;
		while(res)
		{
			if(now==15) now=1;
			b[now]++;
			res--;
			now++;
		}
		long long temp=0;
		for(int j=1;j<=14;j++)
			if(!(b[j]&1)) temp+=b[j];
		ans=max(ans,temp);
	}
	printf("%lld\n",ans);
	return 0;
}

H

Codeforces Round #478 (Div. 2)

题目大意

在一个平面上，0时刻有n个点在一条方程为y=a⋅x+b的直线上，保证这n个点不重合，告诉你n、a和b，然后给你n个点的x坐标和它们所具有的速度矢量Vx和Vy，代表这个点在X方向上的速度为Vx，Y方向上的速度为Vy，某两个点碰撞一次会产生2个单位的权值（碰撞时不会改变路径也不会改变速度），问你这些点一共会产生多少权值。
需要注意的是给的是0时刻的状态，但时间的范围是(−∞,∞)，所以说在0时刻以前的碰撞也会对答案产生贡献。

思路

因为要求碰撞次数，实际上就是看这些点运动轨迹的直线相交得到的交点数量。那我们现在就推导一下相交条件。

设点 $i$ 和 $j$ ，假设他们在 $t$ 时刻相遇,则有
$x_i+V_{x_i}\cdot t\;=\;x_j+V_{x_j}\cdot t$
$y_i+V_{y_i}\cdot t\;=\;y_j+V_{y_j}\cdot t$
移相后两式相除，消去 $t$ 得
$\\ \frac{x_i-x_j}{y_i-y_j}\;=\;\frac{V_{x_j}-V_{x_i}}{V_{y_j}-V_{y_i}}$
$\\ \because i,j$ 两点在同一直线上且该直线斜率为 $a$
$\\ \therefore\frac{y_i-y_j}{x_i-x_j}\;=\;a$
代入上式，得
$\\ \frac{y_i-y_j}{x_i-x_j}\;=\;a\;=\;\frac{V_{y_j}-V_{y_i}}{V_{x_j}-V_{x_i}}$
十字相乘，移相得
$a\cdot V_{x_i}-V_{y_i}\;=\;a\cdot V_{x_j}-V_{y_j}$
上式即为两个点能产生贡献的条件

代码

#include< cstdio >
#include< cstring >
#include< algorithm >
#include< map >
using namespace std;
const int maxn=200005;
map<long long,int> tot;
map<pair<long long,long long>,int> par;
long long n,a,same=0,ans=0;
int main()
{
	scanf("%lld%lld%*d",&n,&a);
	for(int i=1;i<=n;i++)
	{
		long long vx,vy;
		scanf("%*d%lld%lld",&vx,&vy);
		ans+=tot[a*vx-vy];
		tot[a*vx-vy]++;
		same+=par[make_pair(vx,vy)];
		par[make_pair(vx,vy)]++;
	}
	printf("%lld\n",(ans-same)*2);
	return 0;
}

总结

难度不是很大，但看不懂英语题面真的伤。还有就是思路一定要清晰，先想清楚再写，要不然就会写得很混乱，debug也会崩溃，比如比赛时写的F题。