你最愿意做的哪件事，才是你的天赋所在

0%

发表于 Valine：

C

思路

给出一个n*n的矩阵和m个点，现在需要移动到主对角线上，问需要多少次的移动成功，并且不存在两个点在相同的行和相同的列。
根据my，然后如果链成环贡献就+1，否则贡献就是该链的节点个数。

代码实现

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
50
51
52
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
inline bool isprime(ll num)
{if(num==2||num==3)return true;
    if(num%6!=1&&num%6!=5)return false;
    for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
    return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int N = 1e5+10;
int x[N],y[N];
vector<int>g[N];
int ans = 0;
bool vis[N];
void dfs(int u,int fa){
    if(vis[u]){
        if(u==fa)ans++;
        return;
    }
    vis[u]=1;
    if(g[u].empty())return ;
    ans++;
    dfs(g[u][0],fa);
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        ans = 0;
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)vis[i]=1,g[i].clear();
        for(int i=1;i<=m;i++){
            scanf("%d%d",&x[i],&y[i]);
            vis[x[i]]=0;
            if(x[i]!=y[i])g[x[i]].push_back(y[i]);

        }
        for(int i=1;i<=n;i++){
            if(!vis[i])dfs(i,i);
        }
        printf("%d\n",ans);
    }
}
阅读全文 »

发表于 Valine：

题目链接

HDU6241

题目大意

给一棵树全是白色节点，你需要染成黑色，然后有两种类型的规则，一种是当前节点的子树至少有k个节点，另一种是除了当前节点之外必须有y个节点。

思路

二分，二分知道结果了之后，这个题可以转化为这样，这个树最少有$a_i$个节点,最多有(mid-y)个节点，这样就可以求出一个上下界了。
然后判断上下界是否在范围内即可。

阅读全文 »

发表于 Valine：

题目链接

HDU6240

题目大意

给出n个区间和一个长度l，每个区间有一个a，b。
求出能够使得区间全覆盖的同时使得Ans最小，Ans定义如下

思路

没学过分数规划，重新学了一遍,重新看一遍这个式子

阅读全文 »

发表于 Valine：

题目链接

HDU6231

题目大意

求>K的连续区间中的第k大组成一个数组，然后求这个数组的第m大。
很神奇的思路，二分答案，然后用滑动窗口判断是否存在超过m个区间的第k大大于当前的答案即可。
这个思路直接转了一个弯

代码实现

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
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
inline bool isprime(ll num)
{if(num==2||num==3)return true;
    if(num%6!=1&&num%6!=5)return false;
    for(int i=5;1ll*i*i<=num;i+=6){if(num%i==0||num%(i+2)==0)return false;}
    return true;}
const int mod = 1e9+7;
inline ll mul(ll a,ll b,ll c){return (a*b-(ll)((ld)a*b/c)*c+c)%c;}
inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll g = exgcd(b,a%b,y,x);y-=a/b*x;return g;}
inline ll quick_pow(ll a,ll b,ll mod){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll quick_pow(ll a,ll b){ll res=1;while(b){if(b&1)res=mul(res,a,mod);a=mul(a,a,mod);b>>=1;}return res;}
inline ll inv(ll x){return quick_pow(x,mod-2);}
inline ll inv(ll x,ll mod){return quick_pow(x,mod-2,mod);}
inline ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int N = 1e5+10;
int a[N];
int b[N];
int n,k;
ll m;
bool check(int x){
    ll now = 0,j=0,sum=0;
    for(int i=1;i<=n;i++){
        while(now<k&&j<=n){
            j++;
            if(a[j]>=x)
                now++;
        }
        if(j>n)break;
        sum+= n - j + 1;
        if(a[i]>=x)now--;
    }
    return sum>=m;
}
void solve(){
    scanf("%d%d%lld",&n,&k,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(b+1,b+1+n);
    int l = 1,r = n;
    int ans;
    while(l<=r){
        int mid = l+r>>1;
        if(check(b[mid])){
            l = mid + 1;
            ans = mid;
        }else{
            r = mid - 1;
        }
    }
    printf("%d\n",b[ans]);

}
int main(){
    int t;
    scanf("%d",&t);
    while(t--)solve();
}

发表于 Valine：

题目链接

HDU6230

题目大意

找两端回文SRS的形式SR是一个回文，RS是一个回文

思路

用Manacher算法可以简单的求出当前位置i能够扩展的回文长度，接下来就是简单的统计n个区间的相交了。
即两个回文中心i，j,可扩展的长度为leni，lenj，需要满足下面情况

image-20201129202710164

即i，j区间互相包含

计数方法是利用树状数组，将区间长度从小到大排序，然后有序的遍历，每次询问[i+len,i-len-1]的区间值加上，然后再插入树状数组中即可。

阅读全文 »

发表于 Valine：

题目链接

HDU5543

题目大意

给出金条的长度和价值还有一个可以放的长度len，求最大的价值，其中只要金条的中心再len中就可以放上去。

阅读全文 »

发表于 Valine：

题目链接

HDU5550

题目大意

每层楼a个人喜欢打羽毛球，b个人喜欢游泳，但是现在一层楼只能有一个运动场馆，要你安排每一层建什么场馆，是的所有人到自己喜欢的运动场地的距离最小

阅读全文 »

发表于 Valine：

异或线性基

基可以看做是一个空间的坐标轴，例如二维坐标系上每一个点都可以表示为[1,0],[0,1]的表示即

异或线性基则是一组数中的基，他们之间有以下性质

线性基的元素能相互异或得到原集合的元素的所有相互异或得到的值。
线性基是满足性质 1 的最小的集合。
线性基没有异或和为 0 的子集。
线性基中每个元素的异或方案唯一，也就是说，线性基中不同的异或组合异或出的数都是不一样的。
线性基中每个元素的二进制最高位互不相同。

阅读全文 »

发表于 Valine：

Min25筛详解

min25筛有什么用？

目的： 求出$\sum_{i-1}^Nf(i)$的前缀和，其中前置条件为

  • $f(i)$ 当i为素数时，能够用$i^k$表达，例如$f(i)=i^1+i^2+i^3$等形式，常见的有$\phi \quad \mu$函数。

  • $f(i)$是积性函数

怎么求？

分两步走

阅读全文 »