2020杭电多校第一场题解1004,1005,1009

发布于 2020-07-21  0 次阅读


4.Distinct Sub-palindromes

思路:

子回文串最少,n<=3时都是pow(26,n),当n>=4时,可以构造abcabcabc…这样的字符串,因为这样除了a,b,c就不会产生其他的子回文串并且使得最低的为3个,个数都为C(26,3)* A(3,3);

AC Code:

#include<cstdio>
#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
using namespace std;
const double pi = acos(-1.0);
#define INF 0x7f7f7f
// #define TDS_ACM_LOCAL
#define mem(a,b) memset(a , b , sizeof(a))
#define FOR(i, x, n) for(int i = x;i <= n; i++)
int t, n;
void solve(){
    scanf("%d", &n);
    if(n==1)    printf("26\n");
    else if(n==2) printf("676\n");
    else if(n==3) printf("17576\n");
    else    printf("15600\n");
    return ;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    scanf("%d", &t);
    while(t--)  solve();
    return 0;
}

5.Fibonacci Sum(二次剩余,逆元,欧拉降幂)

知识点

思路和代码

9.Leading Robots(模拟栈)

思路:

1、对输入的数据首先加速度按非递减排序,对于加速度相等的按位置非递减排序
2、排序后,如果后面的人的位置在前面的人的后面且加速度更大,则一定会追上前面的人,即可将前面的人出栈
3、在有新机器人进栈时,考虑对于栈中原本有的机器人造成的影响,它是否会在栈中已有的机器人到达第一名以前超过它(这种情况下被超越的机器人相当于被跳过了,因为它还没有到达第一就被淘汰了),也就是比较到达第一的时间
例如:原本是b追a,新入栈一个c,算在b到a之前时c是否超过了b
比较方法:( b . p o s − c . p o s ) / ( c . a − b . a ) < = ( a . p o s − b . p o s ) / ( b . a − a . a ) (b.pos-c.pos)/(c.a-b.a) <= (a.pos-b.pos)/(b.a-a.a)(b.pos−c.pos)/(c.a−b.a)<=(a.pos−b.pos)/(b.a−a.a)
4、对于重复的机器人(起始位置和加速度相等),永远会和重复的并排跑,所以不在答案内,应该除去

AC Code:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=50009;
struct node{
	double pos, a;
	bool operator< (const node &b)const
    {
        if(a!=b.a)
            return a<b.a;
        return pos<b.pos;
    }
}p1[N];
map<pair<int,int>,int>mp;
int n, top, st[N], ans;

bool dis(node a,node b,node c){
	return (b.pos-c.pos)*(b.a-a.a) <= (a.pos-b.pos)*(c.a-b.a);
}

void solve(){
	scanf("%d",&n);
	mp.clear();
	for(int i=1;i<=n;++i)
	{
		scanf("%lf %lf",&p1[i].pos,&p1[i].a);
		pair<int,int> p;							//用map记录输入的对
		p.first=p1[i].pos,p.second=p1[i].a;
		mp[p]++;
	}
	sort(p1+1,p1+n+1);
	top=0;
	for(int i=1;i<=n;++i)		//模拟栈
	{	//分别对应2、3
		while((top>0 && p1[st[top]].pos<=p1[i].pos) || (top>1 && dis(p1[st[top-1]],p1[st[top]],p1[i]))) top--;
		st[++top]=i;
	}
	ans=top;
	for(int i=1;i<=top;i++)		//对应4
	{
		pair<int,int> p;
		p.first=p1[st[i]].pos;
		p.second=p1[st[i]].a;
		if(mp[p]>1) ans--;
	}
	printf("%d\n",ans);	
	return ;
}

int main(){
	int T;
	cin>>T;
	while(T--)	solve();
	return 0;
}


平平无奇的在校大学生