首页 > > 程序设计 > C/C++ >

长乐培训Day4

2019-08-16 07:53:48来源：博客园 阅读 ()

新老客户大回馈,云服务器低至5折

长乐培训Day4

T1 矩阵

题目

【题目描述】

从前有个 n×m 的矩阵，初始时每个位置均为 0。你需要依次执行 q 个操作，每个操作会指定一行或一列，然后将该行或该列的所有元素全部赋为一个相同的值。 输出操作完成后的矩阵。

【输入格式】

第一行包含三个整数 n,m,q，分别表示矩阵的大小和操作次数。

接下来 q 行，每行三个正整数 t,x,y，若 t = 1，则表示将第 x 行的所有元素赋为 y； 若 t = 2，则表示将第 x 列的所有元素赋为 y。

【输出格式】

输出 n 行，每行 m 个由空格隔开的整数，表示操作完成后的矩阵。

【输入样例】

3 3 3

1 1 3

2 2 1

1 2 2

【输出样例】

3 1 3

2 2 2

0 1 0

【数据规模】

对于 20% 的数据，n×m≤25；

对于 30% 的数据，q≤2000；

对于 100% 的数据，n,m≤1000,n×m≤10^5,q≤10^6。 数据保证任一时刻矩阵中所有元素小于 2^31。

解析

第一题依旧是送分模拟题，根据题目的意思直接模拟即可。

最好反着做，这样时间复杂度比较低。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
int read()
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
struct rec{
    int p,x,y;
}s[1000010];
int n,m,q,map[1010][1010];
int main()
{
    //freopen("matrix.in","r",stdin);
    //freopen("matrix.out","w",stdout);
    int t;
    n=read(),m=read(),q=read();
    for(int i=1;i<=q;i++) s[i].p=read(),s[i].x=read(),s[i].y=read();
    for(int i=q;i>=1;i--)
    {
        if(s[i].p==1)
        {
            for(int j=1;j<=m;j++)
                if(!map[s[i].x][j]) map[s[i].x][j]=s[i].y;
        }
        else
        {
            for(int j=1;j<=n;j++)
                if(!map[j][s[i].x]) map[j][s[i].x]=s[i].y;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++) printf("%d ",map[i][j]);
        printf("\n");
    }
    return 0;
    //fclose(stdin);
    //fclose(stdout);
}
View Code

 

 

 

 

 

T2 坐标系

题目

【题目描述】

从前有个平面直角坐标系。 你每次可以向上、向左或向右走，但不能经过重复的点。 求出你从坐标原点出发，走 n 步有多少种不同的方案。 答案对 109 + 7 取模。

【输入格式】

第一行一个整数 n，表示需要走的步数。

【输出格式】

第一行，一个整数，表示答案。

【输入样例】

2

【输出样例】

7

【数据规模】

对于 20% 的数据，n≤10；

对于 40% 的数据，n≤100；

对于 60% 的数据，n≤1000；

对于 80% 的数据，n≤10^6； 对于 100% 的数据，n≤10^9。

解析

这道题目的正解是矩阵快速幂，但是正解讲的人比较多，本蒟蒻就讲讲玄学做法（其实是不会矩阵快速幂）

我们先看下面几组数据（左边是输入，右边是输出）：

1 3

2 7

3 17

4 41

5 99

看出什么规律了吗？没有？没有就对了。

仔细看这一组例子：17=7*2+3

发现了吗？即f[3]=f[2]*2+f[1]（f[n]表示输入为n时的答案）

再在4和5中验证一下，不难得出：f[n]=f[n-1]*2+f[n-2]。

这是什么？递推对吧，所以我们可以直接从f[3]开始向n递推（n=0,1,2时特殊处理）。

结束了吗？并没有，看一下数据范围，n≤109，而f数组最多开到108，

那怎么办呢？答案是：分段打表！

由于最多能开到108，所以我们每段都为108，这样开10段就好了，

在处理每段时，先让n减去相应的数，使其小于等于108，但是由于最后一段还是到了109，

所以我们不妨再把最后一段拆成两段，每段5*107，

每一段的初始值（即f[1]与f[2]（这里的n时处理过的，实际上并不是1与2））我们用上一段计算得出。

亲测能过。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
int read()
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
const int mod=1000000007;
long long n,f[100000001];
int main()
{
    //freopen("coordinate.in","r",stdin);
    //freopen("coordinate.out","w",stdout);
    n=read();
    f[0]=0,f[1]=3,f[2]=7;
    if(n<=100000000)
    {
        for(int i=3;i<=n;i++) f[i]=(f[i-1]*2+f[i-2])%mod;
        cout<<f[n];
    }
    else if(n<=200000000)
    {
        long long w=n-100000000;
        f[1]=426904732,f[2]=402495884;
        for(int i=3;i<=w;i++) f[i]=(f[i-1]*2+f[i-2])%mod;
        cout<<f[w];
    }
    else if(n<=300000000)
    {
        long long w=n-200000000;
        f[1]=133257557,f[2]=861629509;
        for(int i=3;i<=w;i++) f[i]=(f[i-1]*2+f[i-2])%mod;
        cout<<f[w];
    }
    else if(n<=400000000)
    {
        long long w=n-300000000;
        f[1]=855728576,f[2]=167211530;
        for(int i=3;i<=w;i++) f[i]=(f[i-1]*2+f[i-2])%mod;
        cout<<f[w];
    }
    else if(n<=500000000)
    {
        long long w=n-400000000;
        f[1]=314176084,f[2]=716217178;
        for(int i=3;i<=w;i++) f[i]=(f[i-1]*2+f[i-2])%mod;
        cout<<f[w];
    }
    else if(n<=600000000)
    {
        long long w=n-500000000;
        f[1]=59713600,f[2]=0;
        for(int i=3;i<=w;i++) f[i]=(f[i-1]*2+f[i-2])%mod;
        cout<<f[w];
    }
    else if(n<=700000000)
    {
        long long w=n-600000000;
        f[1]=746610433,f[2]=283782829;
        for(int i=3;i<=w;i++) f[i]=(f[i-1]*2+f[i-2])%mod;
        cout<<f[w];
    }
    else if(n<=800000000)
    {
        long long w=n-700000000;
        f[1]=190151629,f[2]=832788477;
        for(int i=3;i<=w;i++) f[i]=(f[i-1]*2+f[i-2])%mod;
        cout<<f[w];
    }
    else if(n<=900000000)
    {
        long long w=n-800000000;
        f[1]=856516568,f[2]=138370498;
        for(int i=3;i<=w;i++) f[i]=(f[i-1]*2+f[i-2])%mod;
        cout<<f[w];
    }
    else if(n<=950000000)
    {
        long long w=n-900000000;
        f[1]=231896493,f[2]=597504123;
        for(int i=3;i<=w;i++) f[i]=(f[i-1]*2+f[i-2])%mod;
        cout<<f[w];
    }
    else
    {
        long long w=n-950000000;
        f[1]=32400151,f[2]=874860932;
        for(int i=3;i<=w;i++) f[i]=(f[i-1]*2+f[i-2])%mod;
        cout<<f[w];
    }
    return 0;
    //fclose(stdin);
    //fclose(stdout);
}
View Code

 

 

 

 

 

T3 a

题目

【题目描述】

有 n 头牛，每头牛有个喝水时间，这段时间它将 . 独 . 占一个 Stall。现在给出每头牛 的喝水时间段，问至少要多少个 Stall 才能满足它们的要求。

【输入格式】

第一行一个正整数 n。 接下来 n 行每行两个正整数 a,b，表示每头牛的喝水时间段。

【输出格式】

一行一个整数，表示最少要安排多少个 Stall 才能满足所有牛的需求。

【输入样例】

3

1 2

2 3

3 4

【输出样例】

2

【数据规模】

对于 100% 的数据，1≤n≤50000,1≤a≤b≤10^6。

解析

讲一个线性做法（代码超级短）。

设一个数组t，t[i]表示时刻i有多少头牛在喝水，在每头牛喝水时间的a处+1，b+1处-1，

最后处理一遍前缀和，找出最大值就行了。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
int read()
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
int n,ans,t[1000100],sum;
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++) t[read()]++,t[read()+1]--;
    for(int i=1;i<=1000000;i++)
    {
        sum+=t[i];
        ans=max(ans,sum);
    }
    cout<<ans;
    return 0;
    //fclose(stdin);
    //fclose(stdout);
}
View Code

 

 

 

 

 

T4 b

题目

【题目描述】

你有一个可以调节明暗度的灯泡，这个灯泡有 n 个明暗度，分别为 1,2,3,··· ,m。

灯泡有一个遥控器，你每按一次遥控器，假设灯泡当前亮度为 x，按一次以后就变成了 x+ 1，如果 x = m，则按一次以后变成 1。

每个灯泡在设计时都有一个按钮，且有一个 舒适值 k，你可以按一次按钮，无论你现在的亮度是多少，你的亮度都会变成 k。按一 次按钮或按一次遥控器都算是操作一次。

现在给你一个序列 a1,··· ,an，一开始你的亮度是 a1，然后你要将亮度调到 a2，再 到 a3，再到 a4...... 最后到 an，完成这个亮度变化的过程会得到一个最小的操作次数 T，

现在问你如何指定舒适值（舒适值指定之后不能改变），使得 T 最小。

【输入格式】

第一行两个正整数 n,m。 第二行 n 个整数，第 i 个整数表示 ai。

【输出格式】

输出一个整数，表示 T 的最小值。

【输入样例】

4

6 1 5 1 4

【输出样例】

5

【数据规模】

对于 60% 的数据，n,m≤3000； 对于 90% 的数据，n,m≤10^5； 对于 100% 的数据，2≤n,m≤10^6,1≤ai ≤m, a[i]不等于 a[i+1]。

解析

看完题目后，第一反应就是从1到m模拟每个k，最后计算出最小的T，这种纯模拟做法可以拿到60分。

其实这题正解是二次差分，以下是巨佬题解。

如果用DP的思想呢？令f[j][i]表示前j个操作舒适度建在i最多能减少多少步。

状态转移方程：

1、如果i不在aj-aj+1之间：f[j+1][i]=f[j][i];

2、否则如果i到aj的距离为x：f[j+1][i]=f[j][i]+x-1;

这个算法是O（n2）的，也是60分。

不着急，我们考虑优化一下这个算法：给一个区间的数加上等差数列。

怎么维护呢？先差分这个数组，举个例子，如果要在0 0 0 0 0 0 0 0 0 0 0中的3-7加一个从1开始的等差数列，

0 0 1 2 3 4 5 0 0 0 0差分后变成0 0 1 1 1 1 1 -5 0 0 0，就是一个区间+1后在末尾减掉最后一个数，

用线段树支持区间修改和单点修改以及单点查询即可，最后再前缀和一次还原初始数组即可。

于是就有了90分（如果优化得好的话也可以100分），再看一遍等差数列差分后的数组，

再差分一次，0 0 1 1 1 1 1 -5 0 0 0就变成了0 0 1 0 0 0 0 -6 5 0 0，发现等差数列差分两次后的数组只涉及三个数的修改。

所以我们每次更新原来的答案数组的差分再差分数组，最后前缀和还原差分数组以及还原原数组即可。

最后记得注意这题是环修改，把一个区间拆成两个来做就可以了。

Code

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;
int read()
{
    int num=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        num=(num<<1)+(num<<3)+ch-'0';
        ch=getchar();
    }
    return num*w;
}
int n,m,a[1000100],t,temp,minn=0x7f7f7f7f;
int main()
{
    //freopen("b.in","r",stdin);
    //freopen("b.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int k=1;k<=m;k++)
    {
        temp=1,t=0;
        while(temp<n)
        {
            if(a[temp+1]>a[temp])
            {
                if(a[temp+1]>=k)
                {
                    if(a[temp+1]-a[temp]>a[temp+1]-k+1) t+=a[temp+1]-k+1;
                    else t+=a[temp+1]-a[temp];
                }
                else
                {
                    if(a[temp+1]-a[temp]>a[temp+1]+m-k+1) t+=a[temp+1]+m-k+1;
                    else t+=a[temp+1]-a[temp];
                }
            }
            if(a[temp+1]<a[temp])
            {
                if(a[temp+1]>=k)
                {
                    if(a[temp+1]+m-a[temp]>a[temp+1]-k+1) t+=a[temp+1]-k+1;
                    else t+=a[temp+1]+m-a[temp];
                }
                else
                {
                    if(a[temp+1]+m-a[temp]>a[temp+1]+m-k+1) t+=a[temp+1]+m-k+1;
                    else t+=a[temp+1]+m-a[temp];
                }
            }
            temp++;
        }
        minn=min(minn,t);
    }
    cout<<minn;
    return 0;
    //fclose(stdin);
    //fclose(stdout);
}
60分代码 
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 1000005;
int n, m, i, j, k, a[MAXN], kk;
long long ans = 0;
long long cnt[MAXN][2];
inline int get()
{
    char c;
    while ((c = getchar()) < 48 || c > 57);
    int res = c - 48;
    while ((c = getchar()) >= 48 && c <= 57)
        res = res * 10 + c - 48;
    return res;
}
inline long long check()
{
    long long pp = 0;
    for(int i = 2; i <= n; i ++)
    {
        if (a[i] > a[i - 1]) pp += a[i] - a[i - 1];
        else pp += a[i] + m - a[i - 1];
    }
    return pp;
}
inline void change(int l, int r, int s, int d)
{
    cnt[l][0] += s;
    cnt[r + 1][0] -= s;
    cnt[l + 1][1] += d;
    cnt[r + 1][1] -= (r - l + 1) * d;
    cnt[r + 2][1] += (r - l) * d;
}
int main()
{
    //freopen("b.in", "r", stdin);
    //freopen("b.out", "w", stdout);
    cin >> n >> m;
    for(i = 1; i <= n; i ++)
        a[i] = get();
    for(i = 2; i <= n; i ++)
    {
        if (a[i] > a[i - 1])
        {
            if (a[i] - a[i - 1] >= 2)
                change(a[i - 1] + 2, a[i], 1, 1);
        }
        else
        {
            if (m - a[i - 1] >= 2) change(a[i - 1] + 2, m, 1, 1), change(1, a[i], m - a[i - 1], 1);
            if (m - a[i - 1] == 1) change(1, a[i], 1, 1);
            if (m == a[i - 1])
            {
                if (a[i] >= 2)
                    change(2, a[i], 1, 1);
            }
        }
    }
    for(i = 2; i <= m + 1; i ++)
        cnt[i][0] += cnt[i - 1][0], cnt[i][1] += cnt[i - 1][1];
    for(i = 2; i <= m + 1; i ++)
        cnt[i][1] += cnt[i - 1][1];
    for(i = 1; i <= m; i ++)
        ans = max(ans, cnt[i][0] + cnt[i][1]);
    cout << check() - ans << endl;
}
AC代码

原文链接:https://www.cnblogs.com/I-Love-You-520/p/11247188.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：类型转换

下一篇：c++ 学习笔记（二）

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签