当前位置：首页 > news >正文

梦熊NOIP第一场

news 2024/11/17 1:56:41

T1

这道题考试时想到正解了，写了一遍发现写挂了，看了一下时间果断写了部分分
部分分还是很好写的，就是序列全是1或0，得分 $30 pt s$

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
const int MOD=1e9+7;
const int N=2e5+10;
int n,m,q;
char s[N];
void work0(){while(q--){int st=read(),k=read();int ans=st;ans=(st+k)%MOD;printf("%lld\n",ans);}
}
int kmi(int a,int b,int p){int res=1;while(b){if(b&1) res=res*a%p;b>>=1;a=a*a%p;}return res;
}
void work1(){while(q--){int st=read(),k=read();int ans=st;ans=(ans%MOD+(m%MOD)*(k%MOD))%MOD;printf("%lld\n",ans);}
}
signed main(){
//	freopen("kingdom3.in","r",stdin);
//	freopen("op.out","w",stdout);n=read(),m=read(),q=read();cin>>(s+1);if(s[1]=='0') work0();else work1();return 0;
}

然后来考虑正解：
，先手玩样例，我们不难发现将序列的每个点和对应点连接起来就会发现形成了一个环，通过证明可以得出最多会形成一个环，证明写在最后。然后我们处理出来每个点到环的距离，并预处理出来倍增数组，从某个点往下跳 $2^k$ 后会到哪一个点，求出环的长度，最后处理一下常数即可，基环树的题，考试时基环树不太会，写了半天还写挂了，真服。常数就是那些周期。
证明：无，金牌哥说，信息不是数学，没必要追求严谨的证明。，只要算法过了就行。谁家好人代码考试把大样例全艹过去了还要把代码的正确性正明一边啊。
下次做这种题要学会转化，脑子动快点。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int read(){int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
const int N = 2e5+5 , mod = 1e9 + 7;
int n , q , nxt[N] , a[N] , dp[65][N] , lg[N];
int m , f[N] , g[65][N];
string s;
void Init() {for (int i = 1; i <= n; i++) {dp[0][i]=nxt[i] ;g[0][i]=f[i];}for (int k = 1; k <= 63; k++) {for (int i = 1; i <= n; i++){dp[k][i]=dp[k-1][dp[k-1][i]] ; g[k][i]=(g[k-1][i] + g[k-1][dp[k-1][i]])%mod;} }return;
}
int Query(int s , int b) {s = (s - 1) % n + 1;int tmp = b , ans = 0;for (int i = 63; i >= 0; i--) {if (tmp & (1ll<<i)){(ans += g[i][s])%=mod ;s = dp[i][s] , tmp^=1ll<<i;}}return ans;
}
signed main () {
//	freopen("in.txt" , "r" , stdin);
//	freopen("out.txt" , "w" , stdout);n=read(),m=read(),q=read();cin >> s;s = " " + s;for (int i = 1; i <= n; i++) {a[i]=a[i - 1];if (s[i]^48) a[i]=i;}for (int i = 1; i <= n; i++) {if (i + m <= n) {if (a[i + m] > i)nxt[i]=a[i + m] , f[i]=a[i + m] - i;else nxt[i]=(i+1-1)%n+1 , f[i]=1;} else {if (a[(i + m - 1ll) % n + 1]) {nxt[i]=a[(i + m - 1ll) % n + 1] ;f[i]=a[(i + m - 1ll) % n + 1]-i+((m+i-1)/n)*n;}else if (a[n]){nxt[i]=a[n] ;f[i]=((m+i-1)/n)*n-i-(n-a[n]);} else {nxt[i]=(i+1-1)%n+1 ; f[i]=1ll;}}}Init();while(q--) {int s=read() , k=read();printf("%lld\n" , (s + Query(s , k))%mod);}return 0;
}

T2

这道题听同只因房大犇讲会了，采用的贪心
我们可以将所有的折扣都换成折扣券
然后就可以贪心了。具体贪心如下：

讲价格按照从小到大排序，方便下面二分
讲折扣力度，即 $v$ 按照从小到大排序
依次遍历每个折扣券，每次查询大于等于当前 $w$ 的第一个数，这里采用 $l o w er b o u n d$
当某点被用过后就删点，用并查集维护
最后注意每次查询的边界情况

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
const int N=1e6+10;
struct node{int a,b, c;
}e[N];
struct quan{int w,v;
}y[N*2];
int n,m;
#define PII pair<int,int>
int as[N];
priority_queue<PII,vector<PII>,less<PII> >q;
bool cmp(node a,node b){return a.a<b.a;
}
bool cmp2(quan a,quan b){return a.v>b.v;
}
int fa[N];
int get(int x){if(x==fa[x]) return x;else return fa[x]=get(fa[x]);
} 
int vis[N];
int ans=0;
signed main(){n=read(),m=read();int tot=m;for(int i=1;i<=n;i++){e[i].a=read(),e[i].b=read();as[i]=e[i].a;ans+=as[i];y[++tot].w=e[i].a,y[tot].v=e[i].a-e[i].b;}for(int i=1;i<=m;i++){y[i].w=read(),y[i].v=read();}for(int i=1;i<=n;i++){fa[i]=i;}sort(as+1,as+1+n);sort(e+1,e+1+n,cmp);sort(y+1,y+1+m+n,cmp2);for(int i=1;i<=m+n;i++){int k=lower_bound(as+1,as+1+n,y[i].w)-as;
//		cout<<y[i].w<<"__:"<<y[i].v<<"   "<<k<<"___"<<"  ";k=get(k);if(k>n||vis[k]||k==0) {
//			cout<<endl;continue;}vis[k]=1;
//		cout<<k<<endl;ans-=y[i].v;if(k==n) continue;fa[k]=get(k+1);}printf("%lld",ans);return 0;
}

考场上我写了贪心特殊性质部分分，如果想出第一个特殊性质的话，那就基本是正解了。但是我写的第二个，从小到大排序后依次遍历即可

#define PII pair<int,int>
priority_queue<PII,vector<PII>,greater<PII> >q;
void work2(){sort(e+1,e+1+n,cmp2);for(int i=1;i<=m;i++){q.push({y[i].w,y[i].v});}for(int i=1;i<=n;i++){if(e[i].a>q.top().first) {ans-=q.top().second;q.pop();}}printf("%lld",ans);
}