头像

一只奇怪的小魔女

东京大学




离线:5小时前


最近来访(486)
用户头像
流光飞舞
用户头像
fujang
用户头像
xiezere
用户头像
lzl_3
用户头像
bobo2010
用户头像
怎样共勉_7
用户头像
墨染樱飞
用户头像
skydegree
用户头像
New_lzc
用户头像
萌混过关
用户头像
OnjoujiToki
用户头像
QQ家族族长
用户头像
Tilbur
用户头像
zdca
用户头像
xiaozihan
用户头像
HH123_
用户头像
Ditto_O
用户头像
cdm
用户头像
no_hard
用户头像
SayonaraGzm


/*
IDA*这个算法的思想其实比A*要好理解很多
简单来说就是我们开一个估计函数这个估计函数的返回值一定比真实值要小这样我们就可以利用这个进行最优化减枝
如果估计函数都无法完成那么真实值一定也无法完成可以直接剪掉
这题由于步数很小答案可能会很大所以我们再用一下之前讲的迭代加深的思想来优化一下搜索
这题我们搜索可以去枚举我们选择的长度以及我们放的位置去搜索
这题我们其实可以不用往前放因为我们往前放会对应前面的一种选法完全没有必要
这题由于每次我们最多改变3个位置的关系所以假设我们有k个错误前后关系那么(k+2)/3就是我们最多要操作的次数
可以看到估计函数的影子了所以我们这题再用IDA*来优化
我们可以用这个(k+2)/3来当成估计函数
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stdio.h>
using namespace std;
const int N = 30;
int di[10][N];
int qi[N];
int n;
int f()
{
    int cnt=0;
    for(int i=1;i<=n-1;i++)
    {
        if(qi[i]+1!=qi[i+1])cnt++;
    }
    return (cnt+2)/3;
}
bool check()
{
    for(int i=1;i<=n-1;i++)
    {
        if(qi[i]+1!=qi[i+1])return false;
    }
    return true;
}
bool dfs(int u,int depth)
{
    if(u+f()>depth)return false;
    if(check())return true;
    for(int len=1;len<=n;len++)
    {
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            for(int k=j+1;k<=n;k++)
            {
                int y=i;
                memcpy(di[u+1],qi,sizeof qi);
                for(int d=j+1;d<=k;d++,y++)
                {
                    qi[y]=di[u+1][d];
                }
                for(int d=i;d<=j;d++,y++)
                {
                    qi[y]=di[u+1][d];
                }
                if(dfs(u+1,depth))return true;
                memcpy(qi,di[u+1],sizeof qi);
            }
        }
    }
    return false;
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {

        cin >> n;
        for(int i=1;i<=n;i++)
        {
            cin >> qi[i];
        }
        int depth=0;
        while(depth<5&&!dfs(0,depth))depth++;
        if(depth>=5) cout << "5 or more"<<endl;
        else cout << depth<<endl;
    }
    return 0;
}



/*
背包问题当我们n*m不大的时候我们就是用经典的dp做法
当m很大n中等的时候一般会根据某种性质贪心来完成
如果m很大但n很小的时候我们可以用dfs爆搜来枚举方案数来完成
爆搜有一种很棒的空间换时间的方式我们可以先爆搜预先处理出来一部分做成一个表
然后爆搜其他部分然后通过查表的方式完成整体的爆搜
这题我们可以预处理出前面的放法能产生的值然后我们搜后面的每次在前面找能组合的小于m的最大值是多少整体取最大
查表的时候我们可以提前把表排序然后二分来查这样就会快不少
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stdio.h>
#define int long long
using namespace std;
int dp[1<<25],ans;
int ai[50];
int m,n;
int cnt;
bool cmp(int a,int b)
{
    return a>b;
}
void dfs(int u,int k,int sum)
{
    if(u>k)
    {
        dp[++cnt]=sum;
        return;
    }
    dfs(u+1,k,sum);
    if(sum+ai[u]<=m)dfs(u+1,k,sum+ai[u]);
}
void dfs1(int u,int sum)
{
    if(u>n)
    {
        int l=1,r=cnt;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(dp[mid]+sum<=m)l=mid;
            else r=mid-1;
        }
        ans=max(ans,dp[l]+sum);
        return;
    }
    dfs1(u+1,sum);
    if(sum+ai[u]<=m)dfs1(u+1,sum+ai[u]);
}
signed main()
{
    cin >> m>>n;
    for(int i=1;i<=n;i++)
    cin >> ai[i];
    sort(ai+1,ai+1+n,cmp);
    int k=n/2+2;
    dfs(1,k,0);
    sort(dp+1,dp+cnt+1);
    dfs1(k+1,0);
    cout << ans<<endl;
    return 0;
}



/*
迭代加深其实是一种限制深度的搜索
当我们可以确定我们要找的答案深度不高而且一定有答案的时候我们可以用迭代加深
迭代加深的方式很简单
我们枚举限制的深度然后去搜索如果搜到了答案就结束没有得到那么就把深度扩大继续搜索
这样的搜索方式只会增加常数但是可以有效的防止时间复杂度指数级别爆炸
我们这题层数其实就是位数我们可以发现答案的位数一定很小所以这题我们可以用迭代加深来搜索
这题是要我们找一个序列
这个序列满足3个性质
递增的
首位是1末位是n
其次中间每位数都是前面两个值的相加
我们搜索一定是按位搜索
枚举每一位可以放的值放好然后跑到下一位
我们可以在每层开一个数组避免重复搜索一个值
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stdio.h>
using namespace std;
int ans[110];
int n;
bool dfs(int u,int depth)
{
    if(u>depth)return false;
    if(u==depth&&ans[u]==n)return true;
    if(u==depth&&ans[u]!=n)return false;
    int st[110]={0};
    for(int i=1;i<=u;i++)
    {
        for(int j=1;j<=u;j++)
        {
            int t=ans[i]+ans[j];
            if(st[t]||t>n||t<ans[u])continue;
            st[t]=1;
            ans[u+1]=t;
            if(dfs(u+1,depth))return true;
        }
    }
    return false;
}
int main()
{
    while(cin>>n)
    {
        if(n==0)break;
        ans[1]=1;
        int depth=2;
        if(n==1)
        {
            cout << 1<<endl;
            continue;
        }
        while(!dfs(1,depth))depth++;
        for(int i=1;i<=depth;i++)
        cout << ans[i]<<" ";
        cout << endl;
    }
    return 0;
}


新鲜事 原文

牙疼真难受┭┮﹏┭┮



/*
基础课里讲的卡特兰数的推导方式和这题一样
这题按照同样的思路推一下就知道答案是C(n+m,n)-C(n+m,m-1);
这题范围比较大所以需要我们去写高精度
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stdio.h>
#include <vector>
#define int long long 
using namespace std;
const int N = 5e5+10;
int sum[N],sum1[N];
int pre[N];
int cnt=0;
int st[N];
int ge(int n,int p)
{
    if(n<p)return 0;
    return n/p+ge(n/p,p);
}
void inti(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(st[i]==0)
        {
            pre[cnt++]=i;
        }
        for(int j=0;pre[j]*i<=n;j++)
        {
            st[i*pre[j]]=1;
            if(i%pre[j]==0)break;
        }
    }
}
vector<int> mul(vector<int> a, int b)
{
    vector<int> c;
    int add=0;
    for(int i=0;i<a.size();i++)
    {
        add=a[i]*b+add;
        c.push_back(add%10);
        add/=10;
    }
    while(add) 
    {
        c.push_back(add%10);
        add/=10;
    }
    while(c.size()>1&&c[c.size()-1]==0)
    {
        c.pop_back();
    }
    return c;
}
vector<int> sub(vector<int> &A, vector<int> &B) 
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);
        if (t < 0) t = 1;
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
signed main()
{
    inti(N-10);
    int n,m;
    cin >> n>>m;
    vector<int> ans1,ans2;
    ans1.push_back(1),ans2.push_back(1);
    for(int i=0;i<cnt;i++)
    {
        int p=pre[i];
        sum[i]=ge(n+m,p)-ge(m,p)-ge(n,p);
    }
    for(int i=0;i<cnt;i++)
    {
        int p=pre[i];
        sum1[i]=ge(n+m,p)-ge(m-1,p)-ge(n+1,p);
    }
    for(int i=0;i<cnt;i++)
    {
        for(int j=1;j<=sum[i];j++)
        {
            ans1=mul(ans1,pre[i]);
        }
    }
    for(int i=0;i<cnt;i++)
    {
        for(int j=1;j<=sum1[i];j++)
        {
            ans2=mul(ans2,pre[i]);
        }
    }
    ans1=sub(ans1,ans2);
    for(int i=ans1.size()-1;i>=0;i--)
    cout << ans1[i];
    cout << endl;
    return 0;
}



/*
看到这题后我才意思到博弈论原来如此的博大精深
博弈论的问题其实都可以用dp来写因为必胜态和必败态都可以递推没有环形依赖
博弈论里的sg函数其实也可以看成一个dp
所以博弈论的题目我们其实完全可以进行衍生为dp问题
复杂博弈论的题目我们有一种比较好用的解法
我们先思考一下这个题目简化版本怎么写然后再思考一下复杂的版本
在简化版本的基础上多加入点状态然后按sg函数的方式递推就可以完成了
这题我们可以先考虑每个堆的数都大于1的情况下我们先手的必胜和必败的情况
我们可以发现我们先手一定可以把堆数和石头总数的奇偶改变
所以我们假设b=堆数+石子的总个数-1
假设这个是奇数那么我们先手一定必胜反之先手一定必败
现在放开限制有a个堆石头个数是1
其他的堆加上对应石头的个数-1是b
这个时候我们去进行sg函数的方式搜索就可以解题了
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stdio.h>
#define int long long 
using namespace std;
const int N = 100;
int f[55][50050];
int dp(int a,int b)
{
    if(f[a][b]!=-1)return f[a][b];
    if(!a)return f[a][b]=b%2;
    if(b==1)return dp(a+1,0);
    if(a&&!dp(a-1,b))return f[a][b]=1;
    if(a>=2&&!dp(a-2,b+(b?3:2)))return f[a][b]=1;
    if(b&&!dp(a,b-1))return f[a][b]=1;
    if(b>=2&&!dp(a,b-1))return f[a][b]=1;
    if(a&&b&&!dp(a-1,b+1))return f[a][b]=1;
    return f[a][b]=0;
}
signed main()
{
    int t;
    cin >> t;
    memset(f,-1,sizeof f);
    while(t--)
    {
        int n;
        cin >> n;
        int a=0,b=0;
        for(int i=1;i<=n;i++)
        {
            int x;
            cin >> x;
            if(x==1)a++;
            else if(b==0)b+=x;
            else b+=x+1;
        }
        if(dp(a,b)) cout << "YES"<<endl;
        else cout << "NO"<<endl;
    }
    return 0;
}



/*
割点:去掉当前节点如果能把图分开那么这个点就是割点
无向图的点双连通分量:不包涵割点的极大连通块
怎么求无向图的点双连通分量这个就不提了
这个题目给我们一个无向图而且还未必连通要我们找去掉一个点能产生的最多多少连通块
如果我们去掉一个割点后原来的一个连通块变成了s个那么我们的答案就是cnt+s-1(cnt是原本就有的连通块个数)
我们只要用tarjan算法在跑点双连通分量的时候开一个全局变量记录一下每个割点能产生的最大连通块s是多少
然后cnt+s-1就是答案了
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stdio.h>
using namespace std;
const int N = 10010;
const int M = 60010;
int s;
int h[N],ne[M],e[M],idx;
int dfn[N],low[N],tim;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int cnt;
int foot;
void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++tim;
    int oi=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j,u);
            low[u]=min(low[u],low[j]);
            if(low[j]>=dfn[u])
            {
                oi++;
            }
        }
        else low[u]=min(low[u],dfn[j]);
    }
    if(u!=foot&&cnt>0)oi++;
    s=max(s,oi);
}
int main()
{
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0&&m==0)break;
        memset(h,-1,sizeof h);
        idx=0;
        cnt=0,s=0;
        tim=0;
        memset(dfn,0,sizeof dfn);
        memset(low,0,sizeof low);
        for(int i=1;i<=m;i++)
        {
            int a,b;
            cin >> a>>b;
            add(a,b);
            add(b,a);
        }
        for(int i=0;i<n;i++)
        {
            if(!dfn[i])
            {
                cnt++;
                foot=i;
                tarjan(i,-1);
            }
        }
        cout << cnt+s-1<<endl;
    }
    return 0;
}



/*
注意以下提到的双连通分量都是指边的
桥的概念:去掉一条边就可以使得整个图不连通那么这个边就是桥
无向图的双连通分量:不包涵桥的极大连通块
无向图的双连通分量其实也可以看成是一个集合中每个点到其他点一定有两条路径这样的集合取极大
求无向图的双连通分量也是用到tarjan算法
首先开一个id数组记录一下每个点是属于哪个连通分量
再开一个dfn数组记录一下每个点的时间戳以及一个Low数组记录一下每个点最大向上可以跑到的时间戳(除了这个点的父节点以外)
接下来我们每次给当前的点加上一个时间戳和low
然后遍历搜索如果下一个点还没有搜过我们就去搜索如果下一个点无法到达比当前更高的点说明当前边以及反边就是桥
最后如果dfn==low那么这就是一个连通块了我们把所有的点加入就好
这个题目给我们一个无向连通图问我们把这个图变成双连通分量至少要加多少条边
这个图已经有的双连通分量里我们不需要加入边所以我们可以把已经有的双连通分量看成一个点
题目就变成了在我们缩点完成后的图(一个树)中问加多少条边可以得到一个双连通分量
答案就是叶子节点的个数加1除2
这题为了求缩点完成之后每个点的度我们要记录下桥
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include<stdio.h>
#include<stack>
#define int long long 
using namespace std;
const int N = 5010;
const int M = 2e5+10;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],tim;
int id[N];
int d[N];
int st[M];
int scc;
void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
stack<int> si;
void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++tim;
    si.push(u);
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
        tarjan(j,i);
        low[u]=min(low[u],low[j]);
        if(low[j]>dfn[u])
        {
            st[i]=1;
            st[i^1]=1;
        }
        }
        else if(i!=(fa^1))
        {
            low[u]=min(low[u],dfn[j]);
        }
    }
    if(dfn[u]==low[u])
    {
        scc++;
        int p;
        do
        {
            p=si.top();
            si.pop();
            id[p]=scc;
        }while(p!=u);
    }
}
signed main()
{
    int n,m;
    cin >> n>>m;
    memset(h,-1,sizeof h);
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin >> a>>b;
        add(a,b);
        add(b,a);
    }
    tarjan(1,-1);
    for(int i=0;i<idx;i++)
    {
        if(st[i])
        {
            d[id[e[i]]]++;
        }
    }
    int cnt=0;
    for(int i=1;i<=scc;i++)
    {
        if(d[i]==1)cnt++;
    }
    cout << (cnt+1)/2<<endl;
    return 0;
}


新鲜事 原文

哈哈哈,中文题我都能读错题目意思,语文白学了


活动打卡代码 AcWing 4084. 号码牌

//这里填你的代码^^
//注意代码要放在两组三个点之间,才可以正确显示代码高亮哦~

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include[HTML_REMOVED]

using namespace std;
const int N = 110;
int p[N];
int find(int x)
{
if(x!=p[x])p[x]=find(p[x]);
return p[x];
}
int ai[200010];
int di[200010];
int main()
{
int n;
cin >> n;
for(int i=1;i<=n;i)
{
cin >> ai[i];
}
for(int i=1;i<=n;i
)
{
cin >> di[i];
}
for(int i=1;i<=n;i)p[i]=i;
for(int i=1;i<=n;i
)
{
if(i+di[i]<=n)
{
int a=find(i),b=find(i+di[i]);
p[a]=b;
}
if(i-di[i]>=1)
{
int a=find(i),b=find(i-di[i]);
p[a]=b;
}
}
int flag=1;
for(int i=1;i<=n;i++)
{
if(find(ai[i])==find(i));
else flag=0;
}
if(flag) cout << “YES”<<endl;
else cout << “NO”<<endl;

return 0;

}