nice party - 题目 - Daimayuan Online Judge
一下子看这道题挺懵的，没想出来该咋搞，虽然也想过要二分，但是没想到如何去写check函数，看了大佬的才知道要如何去贪心，下面就说说check函数是如何写的：c表示已经选了多少个人，若想选的总人数-第i个人的a[i]小于等于c说明满足至多有a[i]个人大于他，若b[i]>=c说明满足至少有b[i]个人小于他，所以这第i个人是符合条件的，可以被选
2022-05-22每日刷题打卡_你好_?的博客-CSDN博客
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
ll t,n,a[200005],b[200005];
bool check(ll x){
ll res=0;
for(ll i=1;i<=n;i++){
if(x-res-1<=a[i]&&res<=b[i]) res++;
}
return res>=x;
}
int main(){
scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i],&b[i]);
ll l=1,r=n,mid,ans=0;
while(l<=r){
mid=l+r>>1;
if(check(mid)) l=mid+1,ans=max(mid,ans);
else r=mid-1;
}
printf("%lld\n",ans);
}
return 0;
}
算的我头都大啦 - 题目 - Daimayuan Online Judge
题面确实有点误导人了，以至于我写了俩小时，一直以为是自己代码的问题，，，
题目的f(x)就是求x后缀的乘积再取模(x+1),g(x,m)解释的还比较清楚，也可以发现g(x,1)=f(x),g(x,2)=f(g(x,1))=f(f(x)),这都是可以递推出来的，而且可以发现数越来越小直到f(x)会和上一个f(x)的值相同，再往下f(x)也不会变了，所以直接算就可以了
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
ll t,n,m,fac[30];
ll f(ll x){
ll cnt=1,res=1,y=x;
if(!y) res=0;
while(y){
res=res*(x%fac[cnt])%(x+1LL);
cnt++;
y/=10;
}
return res;
}
int main(){
fac[0]=1;
for(int i=1;i<=18;i++) fac[i]=fac[i-1]*10LL;
scanf("%lld",&t);
while(t--){
scanf("%lld%lld",&n,&m);
ll ans=0,tmp;
for(int i=1;i<=m;i++){
n=f(n);
if(tmp==n){
ans+=(m-i+1)*n;
break;
}
ans+=n;
tmp=n;
}
printf("%lld\n",ans);
}
return 0;
}
一半相等 - 题目 - Daimayuan Online Judge
枚举ai，把ai当成最小值去求所有大于ai数与ai的差值，然后去求这些差值的因子，因为差值减这些因子总会减没的，去找这些因子的最大值就是k了
2022-05-24每日刷题打卡_你好_?的博客-CSDN博客
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
ll n,a[110];
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
ll ans=0;
for(int i=1;i<=n;i++){
ll minv=a[i],cnt=0,cha=0;
unordered_map<ll,ll>mp;
for(int j=1;j<=n;j++){
if(a[j]==minv) cnt++;
else if(a[j]>minv){
cha=a[j]-minv;
for(int k=1;k*k<=cha;k++){
if(cha%k==0){
mp[k]++;
if(cha/k!=k) mp[cha/k]++;
}
}
}
}
if(cnt>=n/2){printf("-1\n");return 0;}
for(auto x:mp){
if(cnt+x.second>=n/2) ans=max(ans,x.first);
}
}
printf("%lld\n",ans);
return 0;
}
全部相等 - 题目 - Daimayuan Online Judge
只需要管出现的次数就可以，我们去重后按出现次数排升序，然后就可以直接枚举最大值了
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
ll n,a[200005];
unordered_map<ll,ll>mp;
bool cmp(ll a,ll b){
return mp[a]<mp[b];
}
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]),mp[a[i]]++;
sort(a+1,a+n+1);
n=unique(a+1,a+n+1)-a-1;
sort(a+1,a+n+1,cmp);
ll ans=0;
for(int i=1;i<=n;i++) ans=max(ans,(n-i+1)*mp[a[i]]);
printf("%lld\n",ans);
return 0;
}
赢救瓜瓜 - 题目 - Daimayuan Online Judge?字符串哈希
枚举长度len和子串的开头，如果下一个len和该子串相等那么res++，否则就去判断下一个，但这样一段一段的判断太慢，今天新学了字符串哈希，把字符串映射成数值，通过判断数值是否相等就可以判断字符串是否相等；方法：取一个质数(听说这样冲突小)作为进制，然后判断一个字符串t和s的某个字串是否相等可以用前缀和的思想：比如有一个字符串是123456789，还有个字符串是567，想知道这个567和123456789的第5个字符到第7个字符组成的字符串是否相等，那我就用前缀和的思想，用1234567减去1234*1000，这样就得到了567，然后就知道是否相等了；
2022-05-26每日刷题打卡_你好_?的博客-CSDN博客
#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const ll mod=998244353;
ll p=99971,base=13331;
ll t,n,v[50005],bpw[50005];
string s;
ll gethash(ll l,ll r){
ll x=v[l-1]*bpw[r-l+1];
return v[r]-x;
}
int main(){
scanf("%lld",&t);
while(t--){
cin>>s;n=s.size();s=" "+s;
bpw[0]=1;
ll res=0,ans=1;
for(int i=1;i<=n;i++){
res=res*base+s[i];
v[i]=res;
bpw[i]=bpw[i-1]*base;
}
for(int len=1;len<=(n+1)/2;len++){
for(int i=1;i+len<=n;i++){
int j=i+len-1;
res=1;
ll ha=gethash(i,j);j++;
while(j+len-1<=n&&ha==gethash(j,j+len-1)){
res++;
j+=len;
}
ans=max(res,ans);
}
}
printf("%lld\n",ans);
}
return 0;
}
LIS or Reverse LIS?
我一开始想的是要么是一个最大数放中间两边放小数依次递减，或一个最小数放中间两边放大数依次递增，用优先队列来实现，但一直在wa，最后看题解才知道我们只关心数量不关心过程，所以我们发现一个数最多被用两次，在递增序列和递减序列里各用一次，所以一定会存在一个合理的排列使得最小的序列最大值是(cnt+1)/2，我们只要输出这个数就可以了，不用关心他是如何构造的
C. LIS or Reverse LIS?_刷题小萌新的博客-CSDN博客
#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const ll mod=998244353;
ll t,n;
map<ll,ll>mp;
int main(){
scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
ll cnt=0;
mp.clear();
for(int i=1;i<=n;i++){
ll x;
scanf("%lld",&x);
mp[x]++;
if(mp[x]<=2) cnt++;
}
printf("%lld\n",cnt+1>>1);
}
return 0;
}
兔纸 - 题目 - Daimayuan Online Judge
和P3939是一道题，上次用主席树做的，很难理解也很难打，这次用vector做的，看代码就能明白
#include <bits/stdc++.h>
#define ll unsigned long long
using namespace std;
const ll mod=998244353;
int n,m,a[300005];
vector<int>v[300005];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
v[a[i]].push_back(i);
}
while(m--){
int op,x,y,c;
scanf("%d",&op);
if(op==2){
scanf("%d%d%d",&x,&y,&c);
int l=lower_bound(v[c].begin(),v[c].end(),x)-v[c].begin();
int r=upper_bound(v[c].begin(),v[c].end(),y)-v[c].begin()-1;
if(l>r){
printf("0\n");
continue;
}
printf("%d\n",r-l+1);
}
else{
scanf("%d",&x);
if(a[x]==a[x+1]) continue;
int l=lower_bound(v[a[x]].begin(),v[a[x]].end(),x)-v[a[x]].begin();
int r=lower_bound(v[a[x+1]].begin(),v[a[x+1]].end(),x+1)-v[a[x+1]].begin();
v[a[x]][l]++;v[a[x+1]][r]--;
swap(a[x],a[x+1]);
}
}
return 0;
}
