题目1:AcWing 4443.无限区域

给定一个无限大的二维平面，设点 S 为该平面的中心点。

设经过点 S 的垂直方向的直线为 P，如果直线 P 是一个圆的切线，且切点恰好为点 S，那么：

1
2
如果该圆位于直线 P 的右侧，则称之为右圆。
如果该圆位于直线 P 的左侧，则称之为左圆。

现在，给定三个整数 R,A,B，你需要按照右圆、左圆、右圆、左圆…的顺序不断画圆，具体要求如下：

1
2
3
4
第一个右圆的半径等于 R。
每个左圆的半径等于你画的上一个圆的半径乘以 A。
每个右圆（第一个除外）的半径等于你画的上一个圆的半径除以 B（向下取整）。
当你要画的圆的半径等于 0 时，绘画停止。

请你计算，所有画出的圆的面积之和。题目保证绘画会在有限数量的步骤后停止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
using namespace std;

const double PI = 3.1415927;

//画画顺序 右 左 右 左
//当出现画圆半径为0的情况,则退出

int main()
{
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++)
    {
        long long r, a, b;
        scanf("%lld %lld %lld", &r, &a, &b);
        long long ans = r*r;
        //一次执行左右两个操作,因为就算在中途半径清零了,对结果也没有影响
        while(r > 0)
        {
            r *= a;
            ans += r*r;
            r /= b;
            ans += r*r;
        }

        printf("Case #%d: %lf\n",t,PI*ans);

    }

    return 0;
}

题目2:AcWing 3752.更小的字符串

给定一个整数 K 和一个长度为 N 的字符串 S。

已知，字符串 S 是由前 K 个小写字母组成。

现在，请你找出满足下列条件的回文字符串的数量：

长度为 N。
字典序上小于 S。
由前 K 个小写字母组成。
由于满足条件的字符串数量可能很大，所以输出对 1e9+7 取模后的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
using namespace std;

const int MOD = 1e9+7;
const int N = 1e5+10;

typedef long long LL;

int f[N];//f表示有n个位置可以随便取时的分支数

int main()
{
    int T;
    cin>>T;
    for(int t=1;t<=T;t++)
    {
        int n,k;
        scanf("%d %d",&n,&k);
        char s[N];
        cin>>s;
        
        f[0]=1;
        for(int i=1;i<=n;i++)
            f[i]=(LL)f[i-1]*k%MOD;
            
        int res=0;
        int mid=(n+1)/2;//自由度
        for(int i=0;i<mid;i++)
        {
            res+=(LL)(s[i]-'a')*f[mid-i-1]%MOD;
            res%=MOD;
        }
        
        //判断回文串是否小于原串=>前半段全与原s相等的情况
        int y = 0;
        for(int i=mid-1,j=n-1-i;i>=0;i--,j++)
            if(s[i]!=s[j])
            {
                if(s[i]<s[j]) y=1;
                break;
            }
            
        res=(res+y)%MOD;
        printf("Case #%d: %d\n", t, res);
    }
    
    
    return 0;
}