暑期cspj模拟赛2

T1

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    //特判
    if(a == 1)
    {
        cout << 1 << endl;
        return 0;
    }
    long long x = 1;
    for(int i = 1;i <= b;i++) //模拟幂运算的过程
    {
        x *= a;
        if(x > 1e9)
        {
            cout << -1 << endl;
            return 0;
        }
    }
    cout << x << endl;
    return 0;
}

T2

#include <bits/stdc++.h>
using namespace std;

int main(int argc, const char * argv[]) {
    long long k;
    scanf("%lld",&k);
    while (k--) {
        long long n,e,d;
        scanf("%lld%lld%lld",&n,&e,&d);
        long long PsubQ = sqrt((n - e * d + 2) * (n - e * d + 2) - (n * 4));
        long long PaddQ = n - e * d + 2;
        long long P = (PsubQ + PaddQ) / 2;
        long long Q = PaddQ - P;
        if (P * Q == n && e * d == (P - 1) * (Q - 1) + 1 && P && Q) {
            printf("%lld %lld\n",min(P, Q),max(P, Q));
        }else {
            printf("NO\n");
        }
    }
    return 0;
}

T3

#include <bits/stdc++.h>
using namespace std;
#define N (int)1e6 + 100
char str[N];
int c1[N];
int c2[N];
int l1[N];
int l2[N];
int cnt1;
int cnt2;
int dfs(int l,int r) {//记得先看主函数的预处理
    if (c1[r] >= l) {//如果最后一个和 r 同层的 ｜ 在 l 和 r 的范围内
        int ans = dfs(l, c1[r] - 1);
        if (ans == 1) {
            ++cnt1;
            return 1;
        }
        return (ans | dfs(c1[r] + 1, r));
    }
    if (c2[r] >= l) {//如果最后一个和 r 同层的 & 在 l 和 r 的范围内
        int ans = dfs(l, c2[r] - 1);
        if (ans == 0) {
            ++cnt2;
            return 0;
        }
        return (ans & dfs(c2[r] + 1, r));
    }
    if (str[l] == '(' && str[r] == ')') {
        return dfs(l + 1, r - 1);
    }
    return str[l] - '0';
}
int main(int argc, const char * argv[]) {
    scanf("%s",str + 1);
    int len = strlen(str + 1);
    int x = 0;//括号层数
    //l1[x] 代表目前最后一个在 x 层括号的 ｜ 运算符
    //l2[x] 代表目前最后一个在 x 层括号的 & 运算符
    //c1[i] 代表目前和 i 同层的最后一个 | 运算符
    //c2[i] 代表目前和 i 同层的最后一个 & 运算符
    for (int i = 1; i<=len; ++i) {
        if (str[i] == '(') {
            ++x;
        }else if (str[i] == ')') {
            --x;
        }else if (str[i] == '|') {
            l1[x] = i;
        }else if (str[i] == '&') {
            l2[x] = i;
        }
        c1[i] = l1[x];//最后一个在 i 这个位置前且与 i 同层的 | 运算符
        c2[i] = l2[x];//最后一个在 i 这个位置前且与 i 同层的 & 运算符
    }
    int ans = dfs(1, len);
    printf("%d\n%d %d\n",ans,cnt2,cnt1);
    return 0;
}

T4

#include <bits/stdc++.h>

using namespace std;
#define x first
#define y second
int i,j,p,n,k,f[505][105]; // f[i][j]: 前 i 个点，插入了 j 个点后最大长度
pair<int,int>a[505];
int main()
{
	cin>>n>>k;
	for(i=1;i<=n;i++)cin>>a[i].x>>a[i].y;
	sort(a+1,a+n+1);
	for(i=1;i<=n;i++)
	{
		for(j=0;j<=k;j++)f[i][j]=1+j; // 直接在 i 点前插入 j 个点
	}
	// 类似最长上升子序列
	for(i=2;i<=n;i++)
	{
		for(j=i-1;j>=1;j--) // j -> i
		{
			if(a[j].y>a[i].y)continue;
			// 从 j 到 i 要插入 d 个点才能满足
			int d=a[i].x-a[j].x+a[i].y-a[j].y-1;
			for(p=d;p<=k;p++)f[i][p]=max(f[i][p],f[j][p-d]+d+1);
		}
	}
	int ans=0;
	for(i=1;i<=n;i++)ans=max(ans,f[i][k]);
	cout<<ans;
	return 0;
}