彻底自闭ing
F题 K题都比较水就不说了
H题
(因为自己的失误增加了不少罚时,所以一定要让队友拦着我交题)
判断以第i个字符为开头的字符串和以第i + 1个字符为开头的字符串的大小关系
思路:n是1e6,肯定要线性的来做,所以我就从前往后遍历结果TLE了,后来队友说从后往前可以减少向前遍历的时间
#include<bits/stdc++.h>
using namespace std;
char s[1000010],a[1000010];
char ch;
int T,n;
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
scanf("%s",a);
ch = '>';
for(int i = n - 1;i > 0; --i)
{
if(a[i] < a[i - 1]) s[i - 1] = '>',ch = '>';
if(a[i] > a[i - 1]) s[i - 1] = '<',ch = '<';
if(a[i] == a[i - 1]) s[i - 1] = ch;
}
for(int i = 0;i < n - 1; ++i) printf("%c",s[i]);
printf("\n");
}
return 0;
}
B题
给出a b k,求满足n^a * (⌈log2n⌉)^ b <= k 的最大的n
思路:首先二分是很明显的,关键在于精度问题,解决方案有两个
1)用Java大数,可以避免乘爆掉(第一次用Java,感觉好麻烦)
2)巧妙的把乘法移到右边变成除法
//package hello;
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
//PrintWriter out = new PrintWriter(System.out);
int t = sc.nextInt();
int a,b;
BigInteger k,ans,top,low,mid,v1,v2;
BigInteger one = new BigInteger("1");
BigInteger two = new BigInteger("2");
while(t-- > 0)
{
a = sc.nextInt();
b = sc.nextInt();
k = sc.nextBigInteger();
top = k;
low = one;
ans = one;
while(low.compareTo(top) <= 0)
{
mid = low.add(top).divide(two);
v1 = mid.pow(a);
int count = 1;
BigInteger log = two;
while(log.compareTo(mid) < 0)
{
count++;
log = log.multiply(two);
}
v2 = BigInteger.valueOf(count).pow(b);
if(v1.multiply(v2).compareTo(k) <= 0)
{
if(ans.compareTo(mid) < 0)
ans = mid;
low = mid.add(one);
continue;
}
top = mid.subtract(one);
}
System.out.println(ans);
}
}
}
A题
思路:开始的时候想分解质因数啊,统计每个质因子出现的次数求一个前缀和,然后与目标数字的质因子的出现次数比较
后来想这样1e5的二维数组太大了开不了,后来才发现了重要的一点:一个数n的质因子大于sqrt(n)的最多只有一个
所以只需要预处理到100(根号n)的素因子就OK