8.29淘汰赛_淘汰赛 r语言

 先总结一下吧，打的平平，满分五分的话可以打三分。

做了并查集、fylod、stl、处理字符串。

可惜没做出来的   造字（明显dp不熟，不敢往那方面想；递归不行，光顾着找规律）

                            线段树找右面最小值（不静下来好好分析，多取点画图）。

其他的来不及多看题多思考。

需要多练习，多打比赛，调整心态~

• 线段树：找指定位置的 右边 离它最近的 比某个值大的数 的位置

精卫当前所在位置为K(1<=K<=N),精卫会寻找位置在她的西边（不包括她所在的位置K）并且离她距离最近的,石头数大于S(1<=S<=1e9)的石堆

pos在mid的左边的时候，那么我们就知道了在L到mid的区间上有大于S的值，但是我们不知道pos的右边是否有大于S的值，所以我们需要先进入左子树，如果找到了这个值说明pos的右边有大于S的值；否则pos右边没有，这时我们还得去mid的右边寻找另一个大于S的值。需要注意判断这个值是否存在时，引入变量ans，用来判断是否存在，最后再写return ans；

pos在mid的右边的时候我们只能在pos的后面找到位置， 所以必须查询右子树。

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll maxn=1e9+5;
const ll maxm=250010;
ll x,y,ans;
ll n,m,q;
struct node
{
	ll l,r,w;
}t[maxm*4+5];
void build(ll l,ll r,ll k)
{
	t[k].l=l;
	t[k].r=r;
	if(l==r)
	{
		scanf("%lld",&t[k].w);return ;
	}
	ll mid=(l+r)>>1;
	build(l,mid,k*2);
	build(mid+1,r,k*2+1);
	t[k].w=max(t[k*2].w,t[k*2+1].w);
}
void add(ll k)
{
	if(t[k].l==t[k].r)
	{
		t[k].w=0;return ;
	}
	ll mid=(t[k].l+t[k].r)/2;
	if(x<=mid)  add(k*2);
	else add(k*2+1);
	t[k].w=max(t[k*2].w,t[k*2+1].w);
}
void addd(ll k)
{
	if(t[k].l==t[k].r)
	{
		t[k].w=y;return ;
	}
	ll mid=(t[k].l+t[k].r)/2;
	if(x<=mid)  addd(k*2);
	else addd(k*2+1);
	t[k].w=max(t[k*2].w,t[k*2+1].w);
}
ll ask(ll k)
{
	if(t[k].l==t[k].r)
	{
	    if(t[k].w>y)  return t[k].l;
            else          return -1;
	}
	ll mid=(t[k].l+t[k].r)/2;
	ll ans=0;
	if(mid>x&&t[2*k].w>y)
        {
        ans=ask(2*k);
        if(ans==-1)   ans=ask(2*k+1);
        }
	else  ans=ask(2*k+1);
	return ans;
}
int main()
{
    scanf("%lld%lld",&n,&m);
    build(1,n,1);
    while(m--)
    {
        scanf("%lld%lld%lld",&q,&x,&y);
        if(q==1)
        {
            if(x==n||t[1].w<=y)
            {
                printf("-1\n");
            }
            else
            {
                ll ans=ask(1);
                printf("%lld\n",ans);
                if(ans!=-1)
                {
                   x=ans;add(1);
                }
            }
        }
        else if(q==2)
        {
            addd(1);
        }
    }
    return 0;
}

• 仓颉造字

              即第N个字可以如图所示分成4个部分，前3个部分，每个小部分都是字N-1，最后一个部分都是空格(ASCII码为32)

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn=1030;
char dp[12][maxn][maxn];
int main()
{
    int n,cha,mx;
    scanf("%d",&n);
    dp[0][0][0]='*';
    for(int k=1;k<=n;k++)
    {
       cha=(int)pow(2,k-1);
       mx=(int)pow(2,k);
       for(int i=0;i<mx;i++)
       {
          for(int j=0;j<mx;j++)
          {
              if(i>=cha&&j>=cha)  dp[k][i][j]=' ';
              else     dp[k][i][j]=dp[k-1][i%cha][j%cha];
          }
       }
    }
    mx=(int)pow(2,n);
    for(int i=0;i<mx;i++)
    {
        for(int j=0;j<mx-i;j++)
        {
            printf("%c",dp[n][i][j]);
        }
        if(i!=mx-1) printf("\n");
    }
    return 0;
}

 dp不敢想三维；看了同学的代码，觉得自己想的太多了，完全可以按照题意去一块一块填写。这么简单的题没错出来，太浮躁太浮躁

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=500500507;
const int maxn=500000+10;
int n,m;
 
int main()
{
    scanf("%d",&n);
    char s1[1100][1100];
    if(!n)
    {
        printf("*");
        return 0;
    }
    s1[1][1]='*';
    int len=1;
    for(int k=1;k<=n;k++)
    {
        len=k==1?len:len*2;
        for(int i=len+1;i<=len*2;i++)
            for(int j=len+1;j<=len*2;j++)
                s1[i][j]=' ';
         for(int i=1;i<=len;i++)
            for(int j=len+1;j<=len*2;j++)
                s1[i][j]=s1[i][j-len];
         for(int i=len+1;i<=len*2;i++)
            for(int j=1;j<=len;j++)
                s1[i][j]=s1[i-len][j];
    }
    for(int i=1;i<=len*2;i++)
    {
        for(int j=1;j<=len*2;j++)
            printf("%c",s1[i][j]);
        if(i!=len*2)  printf("\n");
    }
    return 0;
}

• KMP应用，next[len]表示字符串最长前缀后缀相同的长度。

1.对于一个字符串S，定义以下n个字符串，S[i]表示一个这样的字符串：截取S的前i个字符，让截取部分的第一个字符接在剩下部分的最后一个字符后面。例：对于字符串S =“abcdef”，S[2]表示字符串“cdefab”。

2.将n个字符串进行分组，相同字符串为一组。

3.定义序列L，表示为每一组的字符串的编号按从小到大排列的序列。

4.按照L的字典序从小到大输出所有分组。

例：S =“abab”，S[0] =“abab”，S[1] =“baba”，S[2] =“abab”，S[3] =“baba”。分组L[]为(0, 2)，(1, 3)。对L数组排序后：L[1]=(0, 2)，L[2]=(1, 3)。因为0比1小。

abab
2
2 0 2
2 1 3

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1000005;
string s;
int ne[maxn];
int len,zu;
void getnext()
{
	int i=0,j=-1;
	ne[0]=-1;
	while(i<len)
	{
		if(j==-1||s[i]==s[j])
		{
			i++;j++;ne[i]=j;
		}
		else j=ne[j];
	}
}
int main()
{
    cin>>s;
    len=s.length();
    getnext();
    int jie=len-ne[len];//找到循环节！！
    int zu;
    if(len%jie!=0)
        zu=len;
    else
        zu=jie;
    printf("%d\n",zu);
    int x=len/zu;
    int y;
    for(int i=1;i<=zu;i++)
    {
       printf("%d ",x);
       y=i-1;
       for(int j=1;j<=x;j++)
       {
           printf("%d ",y);y+=zu;
       }
       printf("\n");
    }
    return 0;
}

• 求因子个数是2的n次 的最小数

对于一个自然数N，都可以分解质因子得到如下形式：p1、p2、p3……pk都是质数。

 筛法求质数
这种方法高效，但内存消耗较大。

思想：去除要求范围内所有的合数，剩下的就是素数了，而任何合数都可以表示为素数的乘积，因此如果已知一个数为素数，则它的倍数  都为合数。
实现：把从1开始的、某一范围内的正整数从小到大顺序排列， 1不是素数，首先把它筛掉。

           剩下的数中选择最小的数是素数，然后去掉它的倍数。

           依次类推，直到筛子为空时结束。

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const ll mod=500500507;
const ll maxn=1e7+5;
bool prime[maxn];
ll  n,ans=1,tp;
priority_queue<ll,vector<ll>,greater<ll> >q;
void judge()
{
    ll cnt=0;
    memset(prime,0,sizeof(prime));
    for(ll i=2;i<maxn;i++)
    {
        if(cnt==n) return ;
        if(!prime[i])
        {
            q.push(i);cnt++;
        }
        for(ll j=i*2;j<maxn;j+=i)
        {
            prime[j]=1;
        }
    }
}
int main()
{
    cin>>n;
    judge();
    while(n--)
    {
        tp=q.top();
        q.pop();
        q.push(tp*tp);
        ans=(ans*tp)%mod;
    }
    cout<<ans<<endl;
    return 0;
}

• 夸父逐日

两个位置同时变化，要记录是否处于过某个状态，需要用结构体存起来，v开二维数组。

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int maxn=1005;
int n,m,l,x,y,a,b;
bool v[maxn][maxn];
vector <int> jnn[maxn];
struct sta
{
    int x,y,d;
};
int main()
{
    scanf("%d%d%d%d%d",&n,&m,&l,&x,&y);
    memset(v,false,sizeof(v));
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&a,&b);
        jnn[a].push_back(b);
        jnn[b].push_back(a);
    }
    queue<sta> q;
    sta tp;
    tp.x=x;tp.y=y;tp.d=0;
    q.push(tp);
    v[x][y]=true;
    while(!q.empty())
    {
    	tp=q.front();
    	if(tp.x==tp.y)  break;
    	q.pop();
    	if(tp.d>l)  continue;
    	sta sc;
    	sc.x=(tp.x+1)%(n+1);
    	sc.y=(tp.y+2)%(n+1);
    	sc.d=tp.d+1;
    	if(!v[sc.x][sc.y])
        {
           q.push(sc);
           v[sc.x][sc.y]=true;
        }
        int len=jnn[tp.x].size();
        for(int i=0;i<len;i++)
        {
            sc.x=jnn[tp.x][i];
            if(!v[sc.x][sc.y])
            {
                q.push(sc);
                v[sc.x][sc.y]=true;
            }
        }
	}
	if(!q.empty()) printf("%d\n",tp.d);
	else  printf("-1\n");
    return 0;
}

• 分割字符串，最大长度为5，求分割相加后的最大值

 
#include<cstdio>
#include<string>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
typedef long long ll;
const ll maxn=1010;
const ll INF=0;
ll dp[maxn][maxn];
ll val[maxn][7];
char s[maxn];
ll n,len,num;
void get()
{
    for(ll i=1;i<=len;i++)
    {
        num=0;
        for(ll j=1;j<=5;j++)
        {
            if(i+j>len+1) continue;
            num*=10;
            num+=(s[i+j-1]-'0');
            val[i][j]=num;
        }
    }
}
int main()
{
    scanf("%s",s+1);
    len=strlen(s+1);
    scanf("%lld",&n);
    if(n>len||len>5*n)
        printf("-1\n");
    else
    {
        for(ll i=0;i<=len;i++)
        {
            for(ll j=0;j<=n;j++)
            {
                dp[i][j]=INF;
            }
        }
        get();
        dp[0][0]=0;
        for(ll i=1;i<=len;i++)
        {
            for(ll j=1;j<=n;j++)
            {
                if(j>i)  break;
                for(ll k=1;k<=5;k++)
                {
                    if(i-k+1<=0) break;
                    if(j>i-k+1) break;
                    dp[i][j]=max(dp[i][j],dp[i-k][j-1]+val[i-k+1][k]);
                }
            }
        }
        printf("%lld\n",dp[len][n]);
    }
    return 0;
}