打完之后体会到自己的水平确实还很低,还需要更加的努力才行

A题

对于我来说的仅有的两个水题,直接模拟即可

F题

二分图匹配模板题

B题

题意:按顺序给出一个几何图形的端点坐标,问它是否是轴对称图形

 

 

D题

找规律难受555~~~

可能是找规律的题做得少(必须要打表)所以很生疏推了一会排列组合之后彻底自闭…

偷一波别人的博客

 第一个答案公式f(n) = (n-1)!+f(n-1)+(n-1)*f(n-1);    
 第二个答案公式 f(n) = f(n-1)+1/n; (由第一个 公式 除于 n!)
1.如果n放在最后,原来的f(n-1)依旧存在不受影响,同时加多(n-1)!个
2.接着对于(n-1)!个排列,把n这个数分别放在1,2,3,4,n-1这些位置,如下f(3)->f(4)

3个数的排列:
123
132
213
231
312
4个数的排列可以看成在3个数排列的基础上添加一位,则4可以放在第一,第二,第三,第四位

①如果放在最后一位则有 (4-1)! 个
1234
1324
2134
2314
3124
3214
②如果是放在第一,第二和第三时则有 (4-1)*f(4-1);
4123   1423   1243
4132   1432   1342
4213   2413   2143
4231   2431   2341
4312   3412   3142
4321   3421   3241 (感觉超极有道理,但是我推不出来QAQ)

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAX 1000005
#define P 1000000007
#define  ll long long int
using namespace std;

ll a[MAX], b[MAX];
double c[MAX];
int n, t;

int main()
{
	scanf("%d",&n);
    a[1] = 1,b[1] = 1,c[1] = 1;
    for (int i = 2; i < MAX; i++)
    {
        a[i] = (a[i - 1] * i) % P;
        b[i] = (a[i - 1] + (i * b[i - 1]) % P) % P;
        c[i] = c[i - 1] + 1.0 / i;
    }
    for (int i = 1; i <= n; i++)
    {
        scanf("%d",&t);
        printf("Case %d: %lld %.6f\n",i,b[t],c[t]);
    }
    return 0;
}

 

E题

题意:给出n个点n-1条边,求出任意两点之间的距离(i到j和j到i都要计算)并求和

思路:这题一看就是求每条边的贡献,也就是说,把这条边去掉树会变成两个独立的子集,两个子集的个数的乘积*2就是这条边需要累加的次数,再乘以边的长度就是对答案的贡献

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;

typedef long long ll;
struct node
{
    ll y,z,next;
}t[200010];
ll head[200010],ans,n,T,tot;
bool vis[100010];
ll x,y,z;

void init()
{
    memset(vis,1,sizeof(vis));
    memset(head,-1,sizeof(head));
    ans = 0;
    tot = 0;
}

void add(ll x, ll y, ll z)
{
    t[++tot].y = y;
    t[tot].z = z;
    t[tot].next = head[x];
    head[x] = tot;
}

ll dfs(ll x)
{
    vis[x] = 0;
    ll cunt = 1;
    for(int i = head[x]; i != -1; i = t[i].next)
    {
        if(vis[t[i].y])
        {
            ll tmp = dfs(t[i].y);
            ans += t[i].z * tmp* (n - tmp) * 2;
            cunt += tmp;
        }
    }
    return cunt;
}

int main()
{
    ll TOT = 0;
    scanf("%lld", &T);
    while(T--)
    {
        init();
        scanf("%lld", &n);
        for(int i = 1;i < n; ++i)
        {
            scanf("%lld%lld%lld", &x, &y, &z);
            add(x, y, z);
            add(y, x, z);
        }
        vis[0] = 0;
        dfs(0);
        printf("Case %lld: %lld\n",++TOT,ans);
    }
    return 0;
}

H题

题意:给出两个区间,现在任取区间的两个数(每个区间取一个),假设第一个区间取数i,第二个区间取数j,判断满足i^j>e的所有i^j的和,其中e是给定的数

思路:肯定和二进制有关啦,数位DP(比赛时DP好像从来没做出来过QAQ)