此贴收录一些比较有意思的思维题 以免以后想起来但是找不到在哪了
思路:主要是两点 发现新加入字符后所形成的新的字符前缀给出的答案是前面已经会存在过的 只需要考虑当前字符串中D 和K的最简比 一直截止到当前字符前缀一共出现了多少次即可 不太好想
AC代码:
/*
*/
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<istream>
#include<ostream>
#include<map>
#pragma GCC optimize(2)
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<int,int>PII;
const int M=2010;
const int mod=1e9+7;
const int N=2e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
typedef long long LL;
int father[N];
int p[N];//素数数组
int find(int x){x==father[x]?x:father[x]=find(father[x]);}
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
bool is_prime(int x)
{
if(x<2)return false;
for(int i=2;i<=x/i;i++)
if(x%i==0)return false;
return true;
}
int gct_prime(int x)
{
int cnt=0;
bool st[N];
memset(st,false,sizeof st);
for(int i=2;i<=x;i++)
{
if(!st[i])p[cnt++]=i;
for(int j=0;j<cnt&&1LL*p[j]*i<=x;j++)
{
st[p[j]*i]=true;
if(i%p[j]==0)break;
}
}
return cnt;
}
int lcm(int a,int b){return a*b/gcd(a,b);};
LL c[M][M];
void init()
{
for(int i=0;i<N;i++)
for(int j=0;j<i;j++)
if(!j)c[i][j]=1;
else c[i][j]=(c[i-1][j-1]+c[i-1][j]);
}
char s[N];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)
{
int n;cin>>n;
cin>>s+1;
map<PII,int>mp;
int d=0,k=0;
for(int i=1;i<=n;i++)
{
if(s[i]=='D')d++;
else k++;
int g=gcd(k,d);
mp[make_pair(k/g,d/g)]++;//以当前这种比例的分割++
cout<<mp[{k/g,d/g}]<<' ';//输出这种比例
}
cout<<'\n';
}
return 0;
}
题意:给定一个长度为n的序列求 一个满足任意两个数的差值的绝对值比当前序列中的最大值大的子序列
思路:由于任意负数的差值的绝对值一定是>=0也大于原本的两个数的所以所有负数都应该算进子列中 通过观察可以发现 所有子列中应该最多只能包含一个正整数 因为 如果有两个正整数 a 和 b的话 a和b的绝对值一定比 a和b中较大的一个数小 说明不满足差值大于最大值的条件 因此只需要考虑 取最小的正整数加入子列的时候 是否能使得负数序列的最小的 差值大于该数即可
AC代码:
/*
Noe
*/
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
typedef long long LL;
const int M=2010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const int N=2e5+10;
int dx[4]={0,1,0,-1};
int dy[4]={-1,0,1,0};
typedef long long LL;
int father[N];
int p[N];//素数数组
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
bool is_prime(int x)
{
if(x<2)return false;
for(int i=2;i<=x/i;i++)
if(x%i==0)return false;
return true;
}
int get_prime(int x)
{
int cnt=0;
bool st[N];
memset(st,false,sizeof st);
for(int i=2;i<=x;i++)
{
if(!st[i])p[cnt++]=i;
for(int j=0;j<cnt&&1LL*p[j]*i<=x;j++)
{
st[p[j]*i]=true;
if(i%p[j]==0)break;
}
}
return cnt;
}
int lcm(int a,int b){return a*b/gcd(a,b);};
LL c[M][M];
void init()
{
for(int i=0;i<N;i++)
for(int j=0;j<i;j++)
if(!j)c[i][j]=1;
else c[i][j]=(c[i-1][j-1]+c[i-1][j]);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("test.in","r",stdin);
int t;cin>>t;
while(t--)
{
int n;cin>>n;
vector<int>a(n+1);
for(int i=1;i<=n;i++)cin>>a[i];//a[i];
// for(int i=1;i<=n;i++)cout
int num0=0;
int numpos=INF;
vector<int>neg;
for(int i=1;i<=n;i++)
{
if(a[i]==0)num0++;
if(a[i]<=0)neg.push_back(a[i]);
if(a[i]>0)numpos=min(numpos,a[i]);
}
/* for(auto c:neg)cout<<c<<' ';
cout<<endl;*/
if(num0>=2)cout<<neg.size()<<endl;
else //<=1
{
sort(neg.begin(),neg.end());//升序排序
int dif=INF;
for(int i=1;i<neg.size();i++)dif=min(dif,abs(neg[i]-neg[i-1]));
if(numpos!=INF)
{
if(dif>=numpos)cout<<neg.size()+1<<endl;
else cout<<neg.size()<<endl;
}else cout<<neg.size()<<endl;
}
}
return 0;
}
