算法

CF955 1982

https://codeforces.com/contest/1982

1 数学思维

/*
我们无需考虑一直加1，而是加一个数到y的倍数这样简化的去想。
*/
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main()
	{
	int t;
	cin>>t;
	while(t--)
		{
		int x,y,k;
		cin>>x>>y>>k;
		while(1)
			{
			if(x==1||k==0)
				//优化：当x=1;一定是加到y，然后y/y=1重复这个过程
				break;
			int s=min(k,y-(x%y));
			x+=s;
			k-=s;
			while(x%y==0)
				x/=y;
			}
		k=k%(y-1);
		x+=k;
		cout<<x<<endl;
		}
return 0;
	}

2 双指针

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e6+100;
int t;
int a[N];
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		int l,r,n;
		cin>>n>>l>>r;
		for(int i=1;i<=n;i++) cin>>a[i];
		int ll=1,rr=0,ans=0,sum=0;
		while(ll<=n&&rr<=n){//保证不越界
			if(sum>=l&&sum<=r){//满足题目要求
				ll=rr+1;//更新区间左端点
				ans++;//答案++
				sum=0;//清零区间和
			}                             
			else if(sum<l){
				rr++;
				sum+=a[rr];//将此数加入当前区间
			}
			else if(sum>r){
				sum-=a[ll];//将此数提出当前区间
				ll++;
			}
		}
		cout<<ans<<endl;
	}
	return 0;//养成好习惯 
}