LeetCode每日一题(5.5)

713. 乘积小于 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
示例 1：

输入：nums = [10,5,2,6], k = 100
输出：8
解释：8 个乘积小于 100 的子数组分别为：[10]、[5]、[2],、[6]、[10,5]、[5,2]、[2,6]、[5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于 100 的子数组。
思路：
滑动窗快模拟

class Solution {
public:
    int numSubarrayProductLessThanK(vector<int>& nums, int k) {
        int sum=1,res=0;
        for(int i=0,j=0;i<nums.size();i++)
        {
            sum*=nums[i];
            while(j<=i&&sum>=k)
            {
                sum/=nums[j];
                j++;
            }
            res+=i-j+1;
        }
        return res;
    }
};

Codeforces

A. Game

#include <bits/stdc++.h>
using namespace std;
int _;
int n;
void solve()
{
	vector<int>v;
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		v.push_back(x);
	}
	int a=-1,b=-1;
	for(int i=0;i<v.size();i++)
	{
		if(v[i]==0)
		{
			a=i;
			break;
		}
	}
	for(int i=v.size()-1;i>=0;i--)
	{
		if(v[i]==0)
		{
			b=i;
			break;
		}
	}
	if(a==-1)cout<<0<<endl;
	else cout<<b+1-a+1<<endl;
}
int main()
{
	cin>>_;
	while(_--)solve();
	return 0;
}

A - Madoka and Math Dad

#include <bits/stdc++.h>
using namespace std;
int _;
int n;
void solve()
{
	cin>>n;
	int m=n/3;
	int r=n%3;
	if(r==1)
	{
		for(int i=1;i<=2*m;i++)
		{
			if(i%2)cout<<1;
			else cout<<2;
		}
		cout<<1<<endl;
	}
	else 
	{
		for(int i=1;i<=2*m;i++)
		{
			if(i%2)cout<<2;
			else cout<<1;
		}
		if(r==2)
		cout<<2<<endl;
		else cout<<endl;
	}
}
int main()
{
	cin>>_;
	while(_--)solve();
	return 0;
}

B - Quality vs Quantity

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int a[N],s[N];
int _;
int n;
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++)s[i]=s[i-1]+a[i];
	for(int i=1;i<=n;i++)
	{
		int blue=s[i],red=s[n]-s[n-i+1];
		if(red>blue)
		{
			cout<<"YES"<<endl;
			return;
		}
	}
	cout<<"NO"<<endl;
}
signed main()
{
	cin>>_;
	while(_--)solve();
	return 0;
}

A - Square Counting

#include <bits/stdc++.h>
using namespace std;
#define int long long
int _;
int n,s; 
void solve()
{
	cin>>n>>s;
	cout<<s/(n*n)<<endl;
}
signed main()
{
	cin>>_;
	while(_--)solve();
	return 0;
}

B - Anti-Fibonacci Permutation

#include <bits/stdc++.h>
using namespace std;
#define int long long
int _;
int n,s; 
const int N=110;
int a[N];
void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)a[i]=n-i+1;
	int f=n;
	for(int j=0;j<n;j++)
	{
		for(int i=1;i<=n;i++)cout<<a[i]<<' ';;
		cout<<endl;
		swap(a[f],a[f-1]);
		f--;
	}
}
signed main()
{
	cin>>_;
	while(_--)solve();
	return 0;
}

A - Doors and Keys

#include <bits/stdc++.h>
using namespace std;
#define int long long
int _;
void solve()
{
	string str;
	cin>>str;
	unordered_set<char>s;
	for(int i=0;i<str.size();i++)
	{
		if(str[i]>='a'&&str[i]<='z')s.insert(str[i]);
		else
		{
			if(s.count(str[i]-'A'+'a')==0)
			{
				cout<<"NO"<<endl;
				return;
			}
		}
	}
	cout<<"YES"<<endl;
}
signed main()
{
	cin>>_;
	while(_--)solve();
	return 0;
}

B. Power Walking

#include <bits/stdc++.h>
using namespace std;
int _;
int n;
void solve()
{
	cin>>n;
	set<int>s;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		s.insert(x);
	}
	for(int i=1;i<=n;i++)
	{
		if(i<=s.size())cout<<s.size()<<' ';
		else cout<<i<<' ';
	}
	cout<<endl;
}
int main()
{
	cin>>_;
	while(_--)solve();
	return 0;
}