有趣的算法题（二）

2021-08-01 09:48:05

Talk is cheap，show me the code
Make Them Equal

题意：给定长度为n的string和一个字符c，每次可把string中下标为x和所有下标是x不是倍数的字符换成字符c
问：要多少次，每次选择哪个下标才能在最少次数内把string字符全部转化为c。

思路：显然，我们知道能利用n和n-1这两个下标，那么最多两步就能完成要求。我们要考虑到0步和1步的情况。

0步：string已然符合要求。
1步：有下标x，下标x和x倍数下标处的字符全为c，那么选择x一步就可以完成(贪心思想)
2步：无符合条件的下标x

#include <bits/stdc++.h>

using namespace std;
int t,n,ans;
char s[300000+10],c;
int main()
{
    for(cin>>t;t;t--)
    {
        ans=0;
        cin>>n>>c>>s+1;
        for(int i=1;i<=n;i++)
        {
            ans=i;
            for(int j=i;j<=n;j+=i)
            {
                if(s[j]!=c)
                {
                    ans=0;
                    break;
                }
            }
            if(ans)
                break;
        }
        if(ans==1)
            cout<<"0"<<endl;
        else if(ans>1)
            cout<<1<<endl<<ans<<endl;
        else
            cout<<2<<endl<<n-1<<" "<<n<<endl;
    }
    return 0;
}

Di-visible Confusion

题意：给定一个数组长度为n，下标从2开始，如果这个Ai%i!=0那么就可以把Ai删除，并且Ai后面的数都往前走。

思路两种
1.我们对于数组进行遍历，碰到第一个不能被目前状态删的数，那么直接删除掉这个数前面的所有数，如此往复，特判：碰到的第一个数下标为2那么显然就无解了
2.分析可知，如果对于一个数n下标为i，能整除小于等于i且大于等于2的所有数，那么就一定无解了。反之就有解。

这题我用vector做不知道为啥总是会报范围RE，找不出问题，，

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false);cout.tie(false);cin.tie(false);
#define freopen freopen("in.txt","r",stdin);
#define YES printf("YES\n");
#define NO printf("NO\n");
ll t,n,a[300000+10];
int main()
{
	for(cin>>t;t;t--)
    {
		cin>>n;
		for(long long i=1;i<=n;i++)
		 cin>>a[i];
		ll now=1,flag=1;
		for(ll i=1;i<=n;i++)
        {
			now=now/__gcd(now,i+1)*(i+1);
			if(now==0)
			{
				NO
				flag=0;
				break;
			}
			if(a[i]%now==0)
			{
				NO
				flag=0;
				break;
			}
		}
		if(flag)
		YES
	}
	return 0;
}

The Number of Imposters没做出来，明天能做出来就写上

Special Numbers
没啥好说的，，
对于第n个数，n转化为2进制就能确定由k的那几个幂相加而来。记得用上快速幂

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false);cout.tie(false);cin.tie(false);
#define freopen freopen("in.txt","r",stdin);
#define YES printf("YES\n");
#define NO printf("NO\n");
int t;
ll fastpow(ll a,ll n)
{
    ll base=a;
    ll res=1;
    while(n)
    {
        if(n&1)
        {
            res=res*base%1000000007;
        }
        base=base*base%1000000007;
        n>>=1;
    }
    return res%1000000007;
}
int main()
{
    freopen
    for(cin>>t;t;t--)
    {
        int n,k,pos=0;
        ll ans=0;
        cin>>k>>n;
        while(n)
        {
            if(n&1)
            {
                ans=ans+fastpow(k,pos);
                ans=ans%1000000007;
            }
            pos++;
            n>>=1;
        }
        cout<<ans%1000000007<<endl;
    }
    return 0;
}

Minimize Distance

题意:给你n个点配送货物，每个点距离已知，每次最多携带k个货物，问你配送过程最少走多少路

思路：简单贪心

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false);cout.tie(false);cin.tie(false);
#define freopen freopen("in.txt","r",stdin);
#define YES printf("YES\n");
#define NO printf("NO\n");
#define debug cout<<1<<endl;
ll a[200000+10],b[200000+10];
int main()
{
   freopen
   int t;
   for(cin>>t;t;t--)
   {
      ll n,cnt1=0,cnt2=0,k,temp;
      ll ans=0;
      cin>>n>>k;
      for(int i=1;i<=n;i++)
      {
          cin>>temp;
          if(temp>=0)
            a[++cnt1]=temp;
          else
            b[++cnt2]=temp*-1;
      }
      sort(a+1,a+cnt1+1);sort(b+1,b+cnt2+1);
      if(a[cnt1]>=b[cnt2])
          ans+=a[cnt1]+b[cnt2]*2;
      else
        ans+=a[cnt1]*2+b[cnt2];
      for(int i=cnt1-k;i>=1;i-=k)
          ans+=a[i]*2;
      for(int i=cnt2-k;i>=1;i-=k)
          ans+=b[i]*2;
      cout<<ans<<endl;
      for(int i=0;i<=cnt1;i++)
             a[i]=0;
      for(int j=0;j<=cnt2;j++)
            b[j]=0;
   }
    return 0;
}

Half of Same

Omkar and Determination
题意：给你个网格，有的被挡住了有的是空的，我们对于任意一个格子只要能每次通过向左或向上走若干次离开这个网格就说这个格子是exitable反之就是unexitable，现在给出l和r，问你从l列到r列如果只告诉你每个网格是exitable或unexitable，你能不能确定这个网格的具体情况。

思路：
首先，我们知道当一个网格的左和上都是unexitable的时候这个网格本身就没法仅通过exitable或unexitable确定是否是空网格，所以如果这种格子出现了，那么l到r如果包含这一列就是无法确认了。反之则可以确认

所以我们需要对

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false);cout.tie(false);cin.tie(false);
#define freopen freopen("in.txt","r",stdin);
#define YES printf("YES\n");
#define NO printf("NO\n");
#define debug cout<<1<<endl;
using namespace std;
int t,n,m;
string s[1000005];
bool st[1000005][21];
int main()
{
    freopen
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>s[i];
    for(int i=1;i<=n-1;i++)
        for(int j=1;j<=m-1;j++)
        if(s[i+1][j-1]=='X'&&s[i][j]=='X')
            st[j][0]=1;
    for(int j=1;j<=20;j++)
        for(int i=1;i<=m-1;i++)
        {
            if(i+(1<<(j-1))-1>m-1)
                st[i][j]=st[i][j-1];
            else
                st[i][j]=st[i][j-1]|st[i+(1<<(j-1))][j-1];
        }
    for(cin>>t;t;--t)
    {
        int l,r;
        cin>>l>>r;
        if(l==r)
        {
              YES
            continue;
        }
        int lg=log2(r-l);
        bool ans=st[l][lg]|st[r-(1<<lg)][lg];
        if(ans)
          NO
        else
          YES
    }
    return 0;
}

CF1594E1 Rubik’s Cube Coloring (easy version)
题意：给定6中颜色和深度为k的满二叉树。问：如果任意连个相邻节点不同色，有多少种涂色方案
如果一个节点是白色的，那么相邻节点不能是白色的或黄色的。
如果一个节点是黄色的，那么相邻节点不能是白色的或黄色的。
如果一个节点是绿色的，那么相邻节点不能是绿色的或蓝色的。
如果一个节点是蓝色的，那么相邻节点不能是绿色的或蓝色的。
如果一个节点是红色的，那么相邻节点不能是红色的或橙色的。
如果一个节点是橙色的，那么相邻节点不能是红色的或橙色的。
也就是说，这个基于魔方现实的二叉树，还是有一定区别的。

思路：
1.数学推导：一共有64n (n=2k-2)
2.DP:
前提：对于起始点为任意一个颜色的方案数，显然总方案数是其乘6
1.对于初始点，我们的方案数为1
2.对于fi，fi则是左子树和右子树的情况做乘法（可以交换组合），在算上采用其他颜色的方案数一共是44=16种。
所以dp[i]=dp[i-1]*dp[i-1]*16;
注意取模

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false);cout.tie(false);cin.tie(false);
#define freopen freopen("in.txt","r",stdin);
#define YES printf("YES\n");
#define NO printf("NO\n");
ll f[65];
int main()
{
    int k;
    f[1]=1;
    cin>>k;
    for(int i=2;i<=k+1;i++)
    {
        f[i]=(f[i-1]*f[i-1])%1000000007*16%1000000007;
    }
    cout<<f[k]*6%1000000007<<endl;
    return 0;
}

至于数学方法就用快速幂做做就行

明天把这个的hard难度做一下，然后再搞一个逻辑题，再搞一个图的题

上一篇：[atAGC044E]Random Pawn


下一篇：stm32使用固件库实现按键输入检测