ABC179 复盘

ABC179_A

题意：

在一个王国，有一种语言叫高桥语，这种语言是用英文小写字母组成的。现在输入一个单词，为字符串 s。如果这个单词的单数形式不是以s结尾的，在末尾加上s。如果这个单词的单数形式是以s结尾的，在末尾加es。保证：1.字符串s不超过1000； 2.均为小写字母。

解析：

很简单，判断字符串末尾字符是否为‘s’即可。
附代码：

ABC179_B

解析：

按照题意模拟即可（注意循环区间为1——n-2） 附代码：

#include <bits/stdc++.h>


using namespace std;  
const int N = 105;  
int n,a[N],b[N];  
int main(void)  
{  
  scanf("%d",&n);  
  for(int i = 1;i <= n;i++)  
  {  
  	scanf("%d%d",&a[i],&b[i]);  
  }  
  for(int i = 1;i <= n-2;i++)  
  {  
  	if(a[i] == b[i] && a[i+1] == b[i+1] && a[i+2] == b[i+2])  
  	{  
  		printf("Yes\n");  
  		return 0;  
  	}  
  }  
  printf("No\n");  
  return 0;  
}

ABC179_C

题意：

给定一个正整数n,求有多少个三元组（A,B,C）使得A*B+C=N.

解析：

暴力做法：三重循环枚举a,b,c,显然超时。
考虑优化：枚举c，再枚举(n-c)的因数，时间复杂度<= O(n根号n),能过。附代码：

#include <bits/stdc++.h>  
using namespace std;  
int n,res;  
int main(void)  
{  
	scanf("%d",&n);  
	for(int c = 1;c < n;c++)  
	{  
		for(int a = 1;a <= sqrt(n-c);a++)  
		{  
			if(a*a == n-c)   
			{  
				res++;  
			}
			else if((n-c)%a == 0)  
			{  
				 res += 2;  
			}  
		}  
	}  
	printf("%d\n",res);  
	return 0;  
}  

ABC179_D

题意：

有 n 个点和 k 个区间 , 数据保证区间之间没有重合部分 。 你现在在点 1 , 每一次可以走 d 步 ( d 为给定区间中的数 ) , 求走到终点的方案数对 998244353 取模的结果。

解析：

能想到O（n^2）DP做法：枚举每一个区间中的每一个端点，累加方案数。此方法超时。
k <= 10,可枚举区间个数，将每一个区间和用前缀和数组表示，复杂度O（n*k），AC。

代码：

#include <bits/stdc++.h>  
using namespace std;  
typedef long long ll;  
const ll N = 2e5+10,MOD = 998244353;  
ll n,k,l[15],r[15],dp[N],sum[N],cnt = 0;  
signed main(void)  
{  
	scanf("%lld%lld",&n,&k);  
	for(ll i = 1;i <= k;i++)  
	{  
		scanf("%lld%lld",&l[i],&r[i]);  
	}   
	dp[1] = sum[1] = 1;  
	for(ll i = 2;i <= n;i++)  
	{  
		for(ll j = 1;j <= k;j++)  
		{  
			dp[i] += (sum[max(0ll,i-l[j])]-sum[max(0ll,i-r[j]-1)]+MOD)%MOD;  
		}  
		sum[i] = (sum[i-1]+dp[i])%MOD;  
	}  
	printf("%lld\n",(dp[n]+MOD)%MOD);  
	return 0;  
}  

ABC179_E

题意：

定义函数f(x,m) = x mod m.
有一个序列a,满足a[1] = x,a[i] = f(a[i-1]^2,m) 求a[1]-a[n]的和。

解析：

直接累加复杂度为O(n),n <= 1e10,超时。 模拟发现：当循环到一个a[i]时，f(a[i-1]^2,m)已在前面出现过了，易得一个循环节，那么用循环节的前缀和乘上循环节的个数加上末尾的数即可。

The End