寒假训练第一场-创新互联

一：前缀和 1.题目：数圈圈题目链接：数圈圈解题思路：

题目给出两个数字a, b，让你求出 a - b 范围内每个数字”圈“的总和。对于这样的区间和问题，直接预处理出前缀和。查询即可

创新互联建站-专业网站定制、快速模板网站建设、高性价比华龙网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式华龙网站制作公司更省心,省钱,快速模板网站建设找我们，业务覆盖华龙地区。费用合理售后完善，十多年实体公司更值得信赖。代码块：

`#includeusing namespace std;
const int N = 1e6 + 10;

int cir[10] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};
int f[N];

int main()
{int n;
    cin >>n;
    
    //根据数据范围，预处理出 1 - 1e6 的前缀和数组
    for(int i = 1; i<= 1000000; i++)
    {int x = i;
        int sum = 0;
        while(x)
        {sum += cir[x % 10];
            x /= 10;
        }   
        f[i] += f[i - 1] + sum; 
    }
    for(int i = 0; i< n; i++)
    {int a, b;
        cin >>a >>b;
        cout<< f[b] - f[a - 1]<< endl;
    }
    return 0;
    }

2.题目：珂朵莉与宇宙题目链接：珂朵莉与宇宙解题思路：

假设暴力处理，那么需要枚举所有的子区间内的和，枚举区间和用前缀和，并枚举理论上符合的 j^2。
即为, s[r] - s[l] = j^2，枚举三个变量肯定超时。
通过变化式子
s[r] - j^2 = s[l], 那么只需要枚举 r, 和 j, 和符合的 s[l], 的个数，因为s[l], 可以循环 r 时，一并维护出，所以优化掉一个枚举。

代码块：

#include#includeusing namespace std;
#define ll long long
const int N=1e6+10;
ll a[N];
ll cn[N];
int main(){ ll n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)a[i]+=a[i-1];
    //mapma;
    cn[0]=1;
    ll sum=0;
    for(int i=1;i<=n;i++){for(int j=0;j*j<=a[i];j++){sum+=cn[a[i]-j*j];
        }
        cn[a[i]]++;
    }
    cout<

3.题目：激光炸弹 
题目链接:激光炸弹 
解题思路：二维前缀和，因为我们要枚举很多子区间，观察数据范围，如果枚举子区间会超时。对于二维区间和的问题，我们使用二维前缀和。
不会二维前缀和可以参考以下文章
二维前缀和
代码块:#includeusing namespace std;
const int N = 5010;

int g[N][N];

int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    int n, m;
    cin >>n >>m;

    for(int i = 0; i< n; i++)
    {int a, b, c;
        cin >>a >>b >>c;
        a++, b++;
        g[a][b] = c;

    }
    
    for(int i = 1; i< N; i++)
        for(int j = 1; j< N; j++)
        {g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1] + g[i][j];
        }
    

    int ans = 0;

    for(int i = m; i< N; i++)
        for(int j = m; j< N; j++)
        {int x2 = i, y2 = j;
            int x1 = i - m + 1, y1 = j - m + 1;

            ans = max(ans, g[x2][y2] - g[x1 - 1][y2] - g[x2][y1 - 1] + g[x1 - 1][y1 - 1]);
        }

    cout<< ans;


    return 0;
}二：差分 
1.题目：校门外的树 
题目链接：校门外的树 
解题思路：首先观察数据范围，考虑暴力是否可做，可做，这里不提供暴力解法。
这个题推荐使用差分来做，来练习差分的使用。
差分可以实现对一个区间的所有数，加减一个数字。对此题，我们假设 0 代表有树木，对一段区间砍树就规定为对一段区间的数 -1。
这样我们就减少了去遍历区间内的每个数字进行减法，而在最后所有操作进行完毕之后，统一计算每个点的值。如果还是0，那么还有树。
代码块:#includeusing namespace std;

const int N=1e4 + 10;

int f[N];
int n, m;

int main()
{cin >>n >>m;
    
    for(int i = 0; i< m; i++)
    {int a, b;
        cin >>a >>b;
        f[a]--;
        f[b + 1]++;
    }

    int ans = 0;

    for(int i = 0; i<= n; i++)
    {f[i] += f[i - 1];
        if(!f[i]) ans++;
    }

    cout<< ans<< endl;


    return 0;
}2.题目：货物种类 
题目链接：货物种类 
解题思路：不难发现这个不同于以前的统计个数吗，而是统计不同种类的数量。所以我们不能对个数进行维护差分数组。
所以我们要对不同的种类维护差分数组，所以我们需要一个一个种类的进行加。并且重复区间不能重复计数，需要区间合并。
所以我们先结构体存下来，进行排序。
因为我们要进行区间合并，所以尽可能 l 的小的排在前面。
区间合并时：分三种情况。
对于同一个种类的区间合并：
1.如果说下一个区间的 l 大于当前维护的区间的 r， 说明这俩区间没有交集，那么 维护区间数组，更新维护的区间
2.否则当前l 小于等于当前维护区间的 r，说明他俩有交集，如果说当前 r >当前维护的区间，那么维护区间 r 需要扩大了。
遇到不同种类了
把之前维护的区间更新差分数组，然后更新区间
代码块:#includeusing namespace std;
const int N = 1e5 + 10;


int f[N];

struct Node
{int l, r, id;
}e[N];

bool bmp(Node x, Node y)
{if(x.id != y.id)
    return x.id< y.id;
    else if(x.l != y.l)return x.l< y.l;
    else return x.r< y.r;
}

int main()
{int n, m;
    cin >>n >>m;

    for(int i = 1; i<= m; i++) cin >>e[i].l >>e[i].r >>e[i].id;

    sort(e + 1, e + m + 1, bmp);

    int st = e[1].l, ed = e[1].r;
    int last = e[1].id;

    for(int i = 2; i<= m; i++)
    {if(last != e[i].id)
        {last = e[i].id;
            f[st]++, f[ed + 1]--;
            st = e[i].l, ed = e[i].r;
        }else
        {if(e[i].l >ed)
            {f[st]++, f[ed + 1]--;
                st = e[i].l, ed = e[i].r;
            }else if(ed< e[i].r) ed = e[i].r;
        }
    }


    f[st]++, f[ed + 1]--;

    int mxx = 0;
    int ans = 0;

    for(int i = 1; i<= n; i++)
    {f[i] += f[i - 1];
        if(f[i] >mxx)
        {mxx = f[i];
            ans = i;
        }
    }


    cout<< ans<< endl;




    return 0;
}
3.题目：放学后茶会的甜点 
题目链接：[放学后茶会的甜点] 
解题思路：优先学习二维差分：
二维差分
二维差分预处理题目对子区间增加 1。题目问取任意大小的区间的大平均甜度，既然是平均甜度，所以我们取大值那一个即可。
因为平均值不会超过大值。
代码块:#includeusing namespace std;

const int N = 1010;

int g[N][N];

int main()
{int n, m, t;
    cin >>n >>m >>t;

    for(int i = 1; i<= t; i++)
    {int x1, y1, x2, y2;
        cin >>x1 >>y1 >>x2 >>y2;

        g[x1][y1] += 1;
        g[x2 + 1][y1] -= 1;
        g[x1][y2 + 1] -= 1;
        g[x2 + 1][y2 + 1] += 1;

    }

    int ans = 0 ;
    
    for(int i = 1; i<= n; i++)
        for(int j = 1; j<= m; j++)
    {g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
        
        ans = max(ans, g[i][j]);
    }


    cout<< ans<
三：贪心 
1.题目：小杰的签到题 
题目链接：小杰的签到题 
解题思路：首先不希望桌子有空闲时间，所以谁先到谁就先排队。
所以我们先排序所有人的到达时间，从到达时间小的开始放置。
假设对于我们当前要放置的队伍来说，肯定放在最先结束的桌子上。找到三个桌子谁先结束。所以我们需要维护每个桌子当前结束时间。
代码块:void solved()
{cin >>n;
    for(int i = 0; i< n; i++) cin >>a[i];
    cin >>m;
    
    //初始化桌子，时间都归0
    for(int i = 0 ;i< 3; i++)
        que[i] = 0;
    
    //排序让先到的进行
    sort(a, a + n);

    for(int i = 0; i< n; i++)
    {int x = a[i];
        int mnn = 1e9; // 找到三个桌子谁最先结束
        int xb = 0;    //记录是第几个桌子
        for(int j = 0; j< 3; j++)
        {if(que[j]< mnn) mnn = que[j], xb = j;
        }
        
        //如果说当前队伍大于等于最先结束的了，那么肯定按照当前队伍到达的时间来开始
        if(x >= mnn)
        {que[xb] = x + m;
        }else que[xb] = mnn + m; 
        //如果我们到达的时候还没有空桌子,那么肯定等空桌子结束我们开始

    }
    
    //三个桌子找到最晚结束的就是我们的答案
    int ans = 0;
    for(int i = 0; i< 3; i++)
    {ans = max(ans, que[i]);
    }

    cout<< ans<< endl;

}2.题目：排座椅 
题目链接：排座椅 
解题思路：首先题目中说所有说话的人是相邻的（上下左右）， 对于竖着相邻的人来说，横着的过道才能影响，对于横着相邻的来说，竖着的过道影响。
对于一条竖着的过道，影响的只能是相邻两列的人，所以贪心的来说，对于每一条过道我们都希望是影响最多的人。
那么统计一下每对人如果要拆开，需要在哪一列 / 一行，防止过道。然后排序从大到小，输出题目要求的过道数量即可。
需要注意的点，题目要求输出过道的位置时，要求从小到大输出。
因为我们需要输出哪个过道被统计的数量最多，所以我们在统计次数的时候，也要标记上是哪个过道，这样排序的时候我们知道是哪个过道最多。
所以使用结构体存。
代码块:#includeusing namespace std;
const int N = 2010;
int hs[N], ls[N];

struct Node
{int id, w;
}he[N], le[N]; //分别统计行和列的次数


bool bmp(Node x, Node y)
{return x.w >y.w;
}


int main()
{int n, m, k, l, d;
    cin >>n >>m >>k >>l >>d;

    for(int i = 0; i< d; i++)
    {int x1, y1, x2, y2;
        cin >>x1 >>y1 >>x2 >>y2;
        
        //上下相邻
        if(x1 == x2)
        {he[min(y1, y2)].w++;
            he[min(y1, y2)].id = min(y1, y2); //避免排序时候不知道是哪个过道
        }else if(y1 == y2) //左右相邻
        {le[min(x1, x2)].w++;
            le[min(x1, x2)].id = min(x1, x2);
        }
    }
    
    //按照统计次数，从大到小
    sort(he, he + N, bmp), sort(le, le + N, bmp);

    
    //因为题目要求输出的时候按照 过道的下标从小到大
    vectorans1, ans2;

    for(int i = 0; i< k; i++)
        ans1.push_back(le[i].id);

    for(int i = 0; i< l; i++)
        ans2.push_back(he[i].id);
        
        
    sort(ans1.begin(), ans1.end()), sort(ans2.begin(), ans2.end());

    for(int i = 0; i< ans1.size(); i++)
        cout<< ans1[i]<< " ";
    cout<< endl;
    for(int j = 0; j< ans2.size(); j++)
        cout<< ans2[j]<< " ";


    return 0;
}3.题目：纪念品分组 
题目链接：纪念品分组 
解题思路：题目规定，最多 2 个物品一组，并且组内大物品不能超过上限值，问你最少多少组。
我们肯定希望尽可能满足 2 个物品一组，所以我们让最小的价值和大的价值组一块是最优解。如果说不能组一块，那大价值只能自己一组。
那么最小值就依次找次小值。
代码块:#includeusing namespace std;
const int N = 30010;

int n, m;
int a[N];

int main()
{cin >>m >>n;

    for(int i = 0; i< n; i++) cin >>a[i];

    sort(a, a + n);

    int l = 0;
    int ans = 0;

    for(int i = n - 1; i >= l; i--)
    {if(i == l)
        {ans++;
            break;
        }

        if(a[i] >= m) ans++;
        else
        {if(a[i] + a[l] >m)
            {ans++;
            }else
            {ans++;
                l++;
            }
        }
    }

    cout<< ans;

    return 0;
}4.题目：巨石滚滚 
题目链接：巨石滚滚 
解题思路：需要注意的点，土球会先撞，再回复，如果说撞的时候就< 0， 那么就失败了。
首先我们可以把所有的障碍分为两类，一类是撞完会增加的，另一类是撞完会减少的。
因为我们希望尽可能的把球的稳定性变成大，然后再减小，这样尽可能满足更多的障碍。
所以我们先撞增加的，再撞减小的。
对于先撞增加的这一类：
因为先撞再增加，所以尽可能的使得撞的值小的放在前面，让球的稳定性尽可能大，避免撞完就小于0。
可能会说，存在一个增加的障碍，但是他的损耗是很大的，肯定会导致撞完就小于0，不能回复。
这样因为他是撞完增加的，我们把他放在前面，是不是最优解？。
因为我们的要求是能够到达终点，而不是通过最多的障碍。
因为这个是损耗大的回复，所以我们肯定把他放在这一类的最后来撞，因为这时已经是极大值的稳定性，如果这时都不能通过，所以肯定不能到达终点。
对于撞完损耗这一类：
因为我们目标是到重点，那么如果到终点，我们大值 + 回复 一定大于所有的损耗 （损耗是一个定值），否则肯定会在路上失败。
那么我们尽可能的让回复多的在前面，这样就尽可能的满足稳定性大。
代码块:#includeusing namespace std;

typedef pairPII; //typedef 同define， pair用法 csdn搜索

#define x first
#define y second


const int N = 500010;

int n, m;

bool bmp1(PII a, PII b)
{return a.x< b.x;
}

bool bmp2(PII a, PII b)
{return a.y >b.y;
}

PII all[N];

void solved()
{cin >>n >>m;

    vectorzh, fu;

    for(int i = 0; i< n; i++)
    {cin >>all[i].x >>all[i].y;

        if(all[i].y - all[i].x >= 0) zh.push_back(all[i]);
        else fu.push_back(all[i]);
    }

    sort(zh.begin(), zh.end(), bmp1);
    sort(fu.begin(), fu.end(), bmp2);

    long long sum = m;

    for(int i = 0; i< zh.size(); i++)
    {if(sum - zh[i].x< 0)
        {cout<< "No"<< endl;
            return;
        }else sum -= zh[i].x, sum += zh[i].y;
    }

    for(int i = 0; i< fu.size(); i++)
    {if(sum - fu[i].x< 0)
        {cout<< "No"<< endl;
            return;
        }else sum -= fu[i].x, sum += fu[i].y;
    }

    cout<< "Yes"<< endl;
}
int main()
{int T;
    cin >>T;
    while(T--) solved();

    return 0;
}
四：二分&二分答案 
1.题目：.完全平方数 
题目链接：完全平方数 
解题思路：暴力的解法就是 从 左区间l到右区间r 找到满足条件数的个数。但考虑到 l和r的大小 可以先预处理出来所有的平方数，然后用二分查找到 处于区间（l，r）满足条件数的范围。即 查找 l和r所在预处理数组中的位置。
代码块:#include#includeusing namespace std;
#define ll long long
vectorv;
void solve(){ll l1,r1;cin>>l1>>r1;
    ll l=0,r=v.size()-1;
    ll k1=-1;
    ll k2=-1;
    //找到第一个 大于等于 l1的
    while(lll mid=(l+r)>>1;
        if(v[mid]>=l1)r=mid;
        else l=mid+1;
    }
    k1=l;
    //找到最后一个 小于等于r1的
    l=0,r=v.size()-1;
    while(lll mid=(l+r+1)>>1;
        if(v[mid]<=r1)l=mid;
        else r=mid-1;
    }
    k2=l;
    cout<for(ll i=0;i*i<=1e9;i++){v.push_back(i*i);
    }
    ll t;cin>>t;
    while(t--)solve();
}2.题目：解方程 
题目链接：解方程 
解题思路：可以使用二分答案 枚举区间（0,100）内的所有数字，注意写好check函数就可以了。这里可以学习经典 浮点数二分的处理方法。
代码块:#include#include#define ll long long
using namespace std;
double n;
double check(double m){ double s=m*m*m*m*2018+m*21+5*m*m*m+5*m*m+14;
    return s;
}
void solve(){cin>>n;
    if(check(100)cout<<"-1"<0.00001){double mid=(l+r)/2.0;
        if(check(mid)>=n)r=mid;
        else l=mid+0.00000001;
    }
    printf("%.4f\n",l);
}
int main(){ll t;cin>>t;
    while(t--){solve();
    }
    return 0;
}3.题目：跳石头 
题目链接：跳石头 
解题思路：使用二分答案，通过枚举 答案 即最短跳跃距离的大值，check（）函数是判断该答案是否可行，是通过 计算 在满足该条件下需要移走岩石的个数，是否满足题目限制的大移动岩石个数。
代码块:#include#include#include#include
#include#include#include#include#define ll long long
const double eps = 1e-4;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a; }//最小公约数__gcd()
using namespace std;
const int NX=1e5+10;
ll x[NX];
ll y[NX];
ll L, N, M;
bool check(ll k)
{ll sum = 0;
    for (int i = 1; i<= N; i++)
    {ll j = i - 1;
        while (y[j] != 0)j--;
        if ((x[i] - x[j])sum++;
            y[i] = 1;
            if (sum >M)return false;
        }
    }
    ll s = N;
    while (y[s] != 0)s--;
    if ((x[N + 1] - x[s])< k)sum++;
    if (sum >M) return false;
    else return true;
}
int main()
{cin >>L >>N >>M;
    for (int i = 1; i<= N; i++)
    {cin >>x[i];
    }
    x[0] = 0;
        x[N + 1] = L;
    ll l = 0;
    ll r = 1e9+10;
    while (l< r)
    {memset(y, 0, sizeof(y));
        ll mid = (l + r) >>1;
        if (check(mid))l =mid+1;
        else r = mid;
    }
    cout<< l-1<< endl;
    return 0;
}
4.题目：借教室 
题目链接：[借教室] 
解题思路：该题目 相当于是 跳石头 的一个拓展，同样是枚举答案 需要通知哪个申请人修改订单。注意check（）函数的书写，在判断答案 是否可行的时候 需要用到 一点差分的知识。 使用差分处理完该申请人 之前的所有订单，然后看是否有不符合要求的情况，即供不应求（需要的教室个数 大于 有空闲的教室个数。
代码块:#include#include#includeusing namespace std;
#define ll long long
const int N=1e6+10;
ll n,m;
ll a[N],b[N],c[N],d[N],e[N]={0};
bool check(int k)
{memset(e,0,sizeof(e));
   for(int i=1;i<=k;i++)
   {   e[c[i]]+=b[i];
       e[d[i]+1]-=b[i];
   }
    for(int i=1;i<=n;i++)
    {e[i]+=e[i-1];
        if(e[i]>a[i])return false;
    }
    return true;
}
int main()
{cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>b[i]>>c[i]>>d[i];
    ll l=1,r=m;
    while(l  ll mid=(l+r)>>1;
       if(check(mid))l=mid+1;
        else r=mid;
    }
    if (l != m){cout<<"-1"<
五：双指针算法 
1.题目：滑动窗口 
题目链接：滑动窗口 
解题思路：双指针经典用法，需要 用两个指针维护一个窗口的长度，然后不停的在一个数组上滑动。首先 需要注意，两个指针必须一起移动，并且 该窗口的长度不会改变，所以 可以使用 滑动窗口去 维护 给定区间长度 的最值。
代码块:#include#include 
#include#include#include#include#include#includeusing namespace std;
#define ll long long
const int N = 1e6+10;
ll p[N], d[N]={0};
ll a[N];
ll q[N];
int main()
{ll n, k; cin >>n >>k;
	ll be = 0, ed =-1;
	for (int i = 1; i<= n; i++)cin >>a[i];
    // be 和 ed 就是 维护 窗口 长度 的两个指针 
	for (int i = 1; i<= n; i++)
	{// 当窗口 长度大于给定值的时候 就将左端点++ 减小窗口长度 维护窗口长度
		if (be<= ed && i - k + 1 >q[be])be++;
        // 维护 窗口的最值 保证最值一定在 数组的最左边 即 be位置
		while (be<= ed && a[q[ed]] >= a[i])ed--;
		q[++ed] = i;
		if (i >= k)printf("%lld ", a[q[be]]);
	}
    cout<// 当窗口 长度大于给定值的时候 就将左端点++ 减小窗口长度 维护窗口长度
		if (be<= ed && i - k + 1 >q[be])be++;
        // 维护 窗口的最值 保证最值一定在 数组的最左边 即 be位置
		while (be<= ed && a[q[ed]]<= a[i])ed--;
		q[++ed] = i;
		if (i >= k)printf("%lld ", a[q[be]]);
	}
    cout<
2.题目：逆序数（归并排序） 
题目链接：[逆序数] 
解题思路：首先我们知道逆序数的定义，然后发现通过 归并排序 的过程，可以计算逆序数，然后 归并排序 其实就是通过递归 在回溯的过程中(通过定义 发现 回溯过程返回的都是 有序数组),，使用 双指针 有序合并两个有序数组。
代码块:#includeusing namespace std;
#define ll long long
const int N=1e5+10;
ll q[N],tmp[N];
ll ans=0;
void merge_sort(ll q[], ll l, ll r)
{if (l >= r) return;

    ll mid =( l + r) >>1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    ll k = 0, i = l, j = mid + 1;
    while (i<= mid && j<= r)
        if (q[i]<= q[j]) tmp[k ++ ] = q[i ++ ];
        else {tmp[k ++ ] = q[j ++ ];ans+=mid-i+1;}

    while (i<= mid) tmp[k ++ ] = q[i ++ ];
    while (j<= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i<= r; i ++, j ++ ) q[i] = tmp[j];
}
int main(){ll n;cin>>n;
    for(int i=1;i<=n;i++)cin>>q[i];
    merge_sort(q, 1, n);
    cout<
六：递归&分治 
1.题目：数的计算 
题目链接：数的计算 
解题思路：首先使用暴力 可以发现f（i）=f（1）+f（2）+…+f(i/2）然后写一个递归函数就可以
但是 发现题目数据 发现这样 暴力过不了，因为 我们做了很多重复的计算，比如 当i为奇数的时候 它能添加数字的情况跟（i-1）添加数字的情况一样，当i为偶数的时候，就相当于在（i-1）的基础上加上了 i可添加的自然数的情况，即（i/2)的情况一样。得到普遍规律： 当i为奇数的时候f（i）=f(i-1) 当i为偶数的时候 f（i）=f（i-1）+f（i/2）.
代码块:#includeusing namespace std;
#define ll long long
ll dfs(ll k){if(k==1)return 1;
    if(k%2)return dfs(k-1);
    else return dfs(k-1)+dfs(k/2);
}
int main(){ll n;cin>>n;
   cout<< dfs(n)<
2.题目：小q的数列 
题目链接：小q的数列 
解题思路：题目有两个要求，第一个要求 就可以直接通过 题目给出的条件进行递归就可以，第二个条件 通过枚举不难发现跟二进制有关系，每次一个新数x的出现一定是在 2的x次方-1的位置出现。
代码块:#include#include#include
#include#define ll long long
using namespace std;
ll solve(ll n)
{if(n==0)return 0;
    if(n==1)return 1;
    return solve(n/2)+solve(n%2);
}
int main()
{ ll t;cin>>t;
    while(t--)
    {ll n;cin>>n;
        ll a=solve(n);
        ll p=pow(2,a)-1;
        printf("%lld %lld\n",a,p);
    }
    return 0;
}3.题目：求先序排列 
题目链接：求先序排列 
解题思路：我们首先 需要学习 树的三种遍历方式（本质计算 对根节点的访问顺序不同），先序排列（根左右） 中序排列（左根右）后序排列（左右根）先序排列的第一个是根节点，后序排列的最后一个节点是根节点。我们可以先根据后序序列找到根节点，然后根据这个根节点来对中序以及后序序列进行分割，于是可以得到左右字数，然后对左子树以及右子树进行递归地处理。
代码块:#include#includeusing namespace std;
#define ll long long
void solve(string s1,string s2){ll k1=s1.size();
    ll k2=s2.size();
    if(k2<=0)return;
      cout<string s1,s2;cin>>s1>>s2;
                solve(s1,s2);
	return 0;
 }七：STL 
1.题目：扫雷游戏 
题目链接：扫雷游戏 
解题思路：根据题意 如果该位置是非地雷格的时候 你需要 计算它周围的地雷个数，如果是地雷格的话 就直接输出‘*’
这里有个小技巧 在地图上 位置的遍历可以用 x和y相对于原来位置数值的变化 直接判断八个方向，在代码中用 d_x和d_y实现。
代码块:#include#include#include
#include#include#include#include#define  ll  long long
using namespace std;
char a[110][110];
ll  b[110][110];
// 八个位置 x 和 y的变化 分别是 下 上 右 左 左上 左下 右下 右上
ll  d_x[10] = {0,0,1,-1,-1,-1,1,1};
ll  d_y[10] = {1,-1,0,0,-1,1,1,-1};
ll  check(int x, int y)
{ll  sum = 0;
	for (int i = 0; i< 8; i++)
	{ll t_x = x + d_x[i];
		ll t_y = y + d_y[i];
		if (a[t_x][t_y] == '*')sum++;
	}
	return sum;
}
int main()
{	ll  x, y;cin >>x >>y;
	for (int i = 1; i<= x; i++){for (int j = 1; j<= y; j++)cin >>a[i][j];
    }
    for (int i = 1; i<= x; i++){for (int j = 1; j<= y; j++)
		{// 如果该位置是非地雷格 则通过 check 函数计算旁边位置地雷的个数
			if (a[i][j] == '?')b[i][j]=check(i, j);
		}
	}
	for (int i = 1; i<= x; i++)
	{for (int j = 1; j<= y; j++)
		{	if (a[i][j] == '*')cout<< a[i][j];
			else cout<< b[i][j];
		}
		cout<< endl;
	}
	return 0;
}2.题目：图书管理员 
题目链接：图书管理员 
解题思路：首先理解题意我们发现我们需要 找到是否能够找到读者需要的书，找到的话输出 图书编码最小的书，反之输出 -1，我们可以 先将图书排序，然后每次进行查询的时候，就遍历一遍 如果存在就输出（因为已经进行了排序，所以能够保证 每次最先找到的是图书编码最小的书），不存在就输出-1.
代码块:#include#include#include
#include#include#include#include#define  ll  long long
using namespace std;
vectorv;
bool cmp(string &s1,string &s2)
{if (s1.size() == s2.size()) return s1< s2;
	else	return s1.size()< s2.size();
}
bool judge2(string &s, string &s1)
{// 使用 双指针 从尾往前判断 是否 图书编码 是否是以读者的需求码结尾
	ll a = s.size()-1;
	ll b = s1.size()-1;
	while (s[a]==s1[b])
	{a--;b--;
		if (a == -1 || b == -1)break;
	}
	if (b == -1)return true;
	else return false;
}
void judge(string &s,int n)
{for (int i = 0; i< v.size(); i++)
	{// 图书编码长度小于读者的需求码 必定不满足，所以直接跳过
		if (v[i].size()< n)continue;
        // 图书编码长度等于读者的需求码
		else if (v[i].size() == n)
		{// 如果 图书编码等于读者的需求码
			if (v[i] == s){		cout<< v[i]<< endl;
				return;
			}
		}
		else
		{// 判读图书编码 是否是 以读者的需求码结尾
			if (judge2(v[i], s)){		cout<< v[i]<< endl;
				return;
			}
		}
	}
	cout<< "-1"<< endl;
}
int main()
{ll n,m;cin >>n>>m;
	for (int i = 1; i<= n; i++){string s;cin >>s;
		v.push_back(s);
	}
    //对书 进行排序
	sort(v.begin(), v.end(),cmp);
	while (m--)
	{ll x;cin >>x;
		string s;cin >>s;
        // 判断 该书是否存在
		judge(s,x);
	}
	return 0;
}
                
     你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
            

            本文名称：寒假训练第一场-创新互联            

            链接URL：http://6mz.cn/article/psgoo.html


    
        其他资讯
        
            
                    java排序算法代码 java排序算法实现
                

                    帝国cms目录绑定域名 帝国cms注入
                

                    谷歌是怎么发明go语言的 谷歌是如何诞生的
                

                    php获取串口数据类型 php获取接口数据
                

                    php数据访问层 php访问记录

网站建设知识

寒假训练第一场-创新互联

其他资讯