问题目录

问题 A: 鸭子游戏

时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
KeineDuck热爱游戏。最近她沉迷于一款名叫“DuckGame”的纸牌。
DuckGame是一款颇有难度的纸牌游戏。在每一轮开始前，会有一些纸牌摆放在玩家的面前，从左到右的第孩堆有ai张纸牌。每张纸牌都是一样的。
游戏开始后，玩家可以选择一个区间[l,r]（包括两个端点），并且把这个区中的每一堆纸牌增加或拿走一张纸牌。若每堆纸牌的个数都相同了，玩家即可获胜。我们称这个步骤为一次操作。
KeineDuck想要知道，她至少要进行多少次操作，才能够获胜。
输入
第一行输入一个正整数n，表示有多少堆纸牌。
接下来一行共n个数，第i个数表示第i堆有多少纸牌。
输出
一个整数，表示至少要多少次操作。
样例输入 Copy
5
2 1 2 3 3
样例输出 Copy
2
提示
样例解释
KeineDuck第一次选择了区间[2,2]，将其中的每堆增加了一张纸牌。
KeineDuck第二次选择了区间[4,5]，将其中的每堆拿走了一张纸牌。
总共用了2次操作。

对于10%的数据，n=2。
对于另外20%的数据，n=6。
对于另外10%的数据，n=10000，且纸牌的数量从左到右单调递增。
对于另外10%的数据，n=100000，且每堆纸牌的个数不超过2。
对于另外20%的数据，n=100000，且每堆纸牌的个数不超过20。
对于最后30%的数据，n=2000000，且每堆纸牌的个数不超过1000。

  • 题意理解：就是把这些数都变成一个相同的数，可以进行两种操作 一种在一个区间+1，另一种在一个区间-1. 问最少进行多少次操作？

  • 思路：差分吧，首先构造出差分数组，我们以第一个数为基点就是都变成这个数。然后构造出dis数组（实质就是与基点的差数组）
    然后就是分两大种情况
    1，当这个差数组（dis数组）小于0时，需要加。
    （1）如果前一个也要加而且加的比这个多的话，这个就不用在加了。
    （2）如果前一个需要加但是加的比这个少，就再加上他们的差（也就是他们的差分数组）。
    （3）如果前一个需要减或者不需要操作，就加上他的差数组（dis数组）
    2，当这个差数组大于零时，需要减。
    （1）如果前一个也要减而且减的比这个还多的话，这个就不用再减了。
    （2）如果前一个需要减但是加的比这个少，就再加上他们的差（也就是他们的差分数组）。
    （3）如果前一个需要加或者不需要操作，就加上他的差数组（dis数组）
    <mark>上述加的数都是他们的绝对值都是正数。</mark>

代码：

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
using namespace std;
const int maxn=2e6+1010;
#define inf 0x3f3f3f3f
const int mod=998244353;
const int MOD=10007;

inline int read() {
	int x=0;
	bool t=false;
	char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')t=true,ch=getchar();
	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
	return t?-x:x;
}

priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;

ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[maxn];
string str,s;

ll qpow(ll a,ll b){
	ll sum=1;
	while(b){
		if(b&1) sum=sum*a%100;
		b>>=1;
		a=a*a%100;
	}
	return sum;
}
int main() {
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
		sum+=a[i];
	}
	sum/=n;
	a[0]=a[1];
	for(int i=1;i<=n;i++)
		b[i]=a[i]-a[i-1];
	
	for(int i=1;i<=n;i++)
	{
		dis[i]=dis[i-1]+b[i];
		if(dis[i]<0){
			if(dis[i]>dis[i-1]) continue; 
			else if(dis[i]<dis[i-1]&&dis[i-1]<0){
				ans+=abs(b[i]);
			// cout<<i<<"-"<<endl;
			}else if(dis[i]<dis[i-1]&&dis[i-1]>=0){
				ans+=abs(dis[i]);
				//cout<<"-"<<abs(b[i])<<endl;
			}
		}else if(dis[i]>0){
			if(dis[i]<dis[i-1])continue;
			else if(dis[i]>dis[i-1]&&dis[i-1]>0){
				ans+=abs(b[i]);
			// cout<<i<<"+"<<abs(b[i])<<endl;
			} else if(dis[i]>dis[i-1]&&dis[i-1]<=0){
				ans+=abs(dis[i]);
				//cout<<i<<"+"<<abs(dis[i])<<endl;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

问题 B: 循环

时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
给定x，有与x的关系式：ai=xi (mod 100) 。
用程序求出循环节。

输入
第一行一个正整数x（x ≤ 1000）
输出
从i等于1开始，输出a[i]，空格隔开，直到输出有重复为止。
样例输入 Copy
354
样例输出 Copy
54 16 64 56 24 96 84 36 44 76 4 16

思路：简单的暴力枚举就完了，没啥好说的。
代码：

#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
using namespace std;
const int maxn=2e6+1010;
#define inf 0x3f3f3f3f
const int mod=998244353;
const int MOD=10007;
 
inline int read() {
    int x=0;
    bool t=false;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
 
priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;
 
ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[maxn];
string str,s;
 
ll qpow(ll a,ll b){
    ll sum=1;
    while(b){
        if(b&1) sum=sum*a%100;
        b>>=1;
        a=a*a%100;
    }
    return sum;
}
int main() {
    cin>>n;
    for(int i=1;;i++)
    {
        sum=qpow(n,i);
        if(a[sum]){
        cout<<sum<<endl;
        break;
        }
        else{
            cout<<sum<<" ";
            a[sum]++;
        }
    }
    return 0;
}

问题 C: 漫步

时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
有n组人在一条无尽的小路上漫步，每组人都有一个初始位置和速度，一组人总是会以相同的速度进行漫步，且所有人漫步的方向都相同。
因为这是一条小路，所以当一个速度更快的赶上另一组速度较慢的人时，这两组会合并成一组，而合并成的这个新组的速度与原来两组中速度较慢的那组速度相同，他们会以这个速度继续往前跑。
当然跑到最后的时候，没有任何一组会与其他组再合并。这个时候还剩下几组人？

输入
第一行两个数n，表示初始组数。
接下一行n行每行两个数d、v，表示这组的初始位置和初始速度。
数据保证所有组初始位置不同，并且读入按从小到大的顺序给出。

输出
一行一个数ans,表示最后还剩下几组。
样例输入 Copy
5
0 1
1 2
2 3
3 2
6 1
样例输出 Copy
2
提示
对于30%的数据，n≤2000。
对于100%的数据，n≤105，0≤d≤109，1≤v≤109。

代码：

  • 思路：从后边往前遍历：
    1，后面的数（y）控制前面的（x）。如果前一个数（x）大于这个数（y），这个数（y）就可以控制前一个数（x）（也就是前一个能追上这个），并把前一个数（x）赋值成这个数（y）。
    2，如果前一个数（x）小于等于这个数（y）（书名前一个永远追不上这个） 就生成另一堆。
    最后输出一共几堆。 
#include <map>
#include <queue>
#include <string>
#include<iostream>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <math.h>
typedef long long ll;
using namespace std;
const int maxn=2e5+1010;
#define inf 0x3f3f3f3f
const int mod=998244353;
const int MOD=10007;
 
inline int read() {
    int x=0;
    bool t=false;
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
 
priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大 
priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小
map<ll,ll>mp;
 
ll n,m,t,l,r,p;
ll sum,ans,res,cnt,flag,maxx,minn;
bool isprime[maxn];
ll a[maxn],b[maxn],c[maxn];
ll dis[maxn],vis[maxn];
ll dp[1010][1010];
string str,s;
 
struct king {
    ll d,v;
}q[maxn];
 
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&a[i],&b[i]);
    sum=0;
    for(int i=n;i>=1;i--)
    {
        if(b[i]<b[i-1]){
            b[i-1]=b[i];
         }else {
            //cout<<b[i]<<endl;
            sum++;
         }
     }
     cout<<sum<<endl;
    return 0;
}