#include 

using namespace std;

int main() {
    int n,k;
    cin>>n>>k;
    if(n-k

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

B.Watches

• 题意

  • 给n个表，给定每个表的价格，有m元钱
  • 买表的价格为，手表本身的价钱+购买表的数量*表原始给的顺序i
  • 问最多可以买多少个手表

• 题解

  • 研究对象是手表的时候，不能确定哪些价值更小，因为k是不确定的
  • 研购买究数量k时，k对买表价格的影响是单调的，所以可以二分k。k确定的情况下所有表的价格确定，直接算出价格排序后check前k个能不能买下来即可。

• 代码

#include 
#include 

using namespace std;
#define int long long
const int N=1e5+5;

int n,m;
int a[N],b[N];//注意开两个数组，一个存原价值，一个用来check时计算新价值排序的，因为需要check多次，所以只用一个数组不行

bool check(int k) {
    for(int i=1;i<=n;i++) b[i]=a[i]+k*i;//计算新价值
    sort(b+1,b+1+n);//排序
    
    int res=0;
    for(int i=1;i<=k;i++) {//检验是否能买下
        res+=b[i];
        if(res>m) return false;
    }
    return true;
}

void solve() {
    for(int i=1;i<=n;i++) cin>>a[i];
    
    int l=0,r=n;
    while(l>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<>n>>m) solve();
    
    return 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
33
34
35
36
37
38
39
40
41

H.Cutting Papers

• 题意

  • 求下两式图形的并集面积
    { ∣ x ∣ + ∣ y ∣ + ∣ x + y ∣ < = n x 2 + y 2 = n 2 4
    {|x|+|y|+|x+y|<=nx2+y2=n24" role="presentation" style="position: relative;">{|x|+|y|+|x+y|<=nx2+y2=n24$$\{\begin{array}{l}|x|+|y|+|x+y|<=n\\ x^2+y^2=\frac{n^2}{4}\end{array}$$
    {∣x∣+∣y∣+∣x+y∣<=nx2+y2=4n2​​

• 题解

  • 如图，为半个圆+两个小正方形的面积

• 代码

#include
using namespace std;
const double pi=3.1415926535897932385;
//可以写成 pi=acos(-1);
int main() {
    long long n;
    while(cin>>n)
        printf("%.12f\n", n * n * pi / 8.0 + n * n / 2.0);
    return 0;
}
1
2
3
4
5
6
7
8
9
10

D.Birds in the tree

• 题意

  • 给01字符串表示一棵树所有节点的颜色，以及树的边
  • 求有多少个连通子图使得度为1的节点颜色相同

• 题解

  • 树形dp

  • f[u,0/1]表示以u为根的子树，u在联通块内，联通块内度数为1的颜色为0/1的联通块数量

  • 假设u点颜色为0（1一样）
    $$\begin{gathered} f[u,0]=\prod _{v\in chil{d}_u}(f[v,0]+1) \\ f[u,1]=\prod _{v\in chil{e}_u}(f[v,1]+1)-\sum _{v\in chil{d}_u}f[v,1]-1 \end{gathered}$$

  • 状态转移方程解释：

    f[u,0]，对于根节点u的所有孩子都可以选或者不选，即每个孩子对答案的贡献为f[v,0]+1，由乘法原理可以得到上式。并且因为u的颜色为0，所以即使所有孩子都不选联通块只剩u这一个1度的节点也是符合要求的。

    f[u,1]，一样对于孩子节点可以选和不选然后乘法原理，但是要减去只剩自己的情况，因为颜色不对。同时排除有根节点只有1度的情况，因为根节点不符合颜色要求，所以-1*f[v,1],(排除如下图所示的情况)

  • $$ans=\sum _{i=1}^n(f[i,1]+f[i,0])，从底向上算，dfs时实则是这样算$$

• 代码

#include 
#include 

using namespace std;
const int N=3e5+10,mod=1e9+7;
typedef long long LL;

char s[N];
int n,pos[N];
int h[N],e[2*N],ne[2*N],idx;//注意无向边的要开两倍范围
LL ans,f[N][2];//答案，动态数组

void add(int a,int b) {
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u,int fa) {//因为加边会加入父亲节点，而题目要求的是子树，所以传入父节点用来排除计算了父节点
    f[u][0]=f[u][1]=1;//初始化为1，才能计算
    LL sum=0;
    for(int i=h[u];~i;i=ne[i]) {//遍历所有子节点
        int j=e[i];
        if(j!=fa) {
            dfs(j,u);//递归计算
            sum=(sum+f[j][pos[u]^1])%mod;
            f[u][0]=(f[u][0]*(1+f[j][0]))%mod;//乘法原理
            f[u][1]=(f[u][1]*(1+f[j][1]))%mod;
        }
    }
    f[u][pos[u]^1]--;//因为一开始预支了1给这个不符合的，所以再减回来
    ans=(ans+f[u][0]+f[u][1]-sum+ mod) % mod;//因为上面-1过，回溯回去计算的时候，相当于u这个子节点不选的方案数已经减掉了，所以不需要f[u][pos[u]^1]-sum，但是ans是全局答案，所以需要再减sum
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>n;cin>>s+1;
    for(int i=1;i<=n;i++) pos[i]=s[i]-'0';//记录每个点的颜色
    int a,b;
    memset(h,-1,sizeof h);//初始化表头
    for(int i=1;i>a>>b;
        add(a,b);add(b,a);//无向边
    }
    
    dfs(1,1);//从根开始算
    cout<