2018ccpc女生专场

彻底自闭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