1024测试

每日一测系列，感觉身体被掏空

文章目录

T1 某位歌姬的故事T2 ことりのおやつT3 诗歌总结

T1 某位歌姬的故事

很鬼畜的一道题QAQ 考试的时候，花了二十多分钟思考排列组合想骗个暴力分 蓝鹅最后把自己绕晕了 想给自己唱首凉凉 orz巨菜

正解是dp:

首先将所有区间按照音高限制从小到大排序，然后将每个位置的最高音高处理出来，然后对于每一个不同的音高限制拿出所有对应的位置和限制区间做一个$dp$，不同音高之间的方案数用乘法连接。 至于$dp$，方法有很多，可以设 $f(i,j)$ 表示满足了前$i$个区间，处理到了位置 $j$，且$j$上放的是最大值，$j$后不能再出现最大值。转移本来是$O(n)$的，可以用前缀和优化至$O(1)$（确切地说是$O(logn)$因为有个快速幂） #include<cstdio> #include<cstring> #include<iostream> #include<cstdlib> #include<vector> #include<queue> #include<stack> #include<algorithm> #include<deque> #include<cmath> #include<cctype> #define ll long long #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 #define mod 998244353 using namespace std; const int maxn=1005; const int inf=1000000000+9; ll ans; int T,n,m,A,mx,num; int p[maxn],w[maxn],t[maxn]; int a[maxn],L[maxn],f[maxn][maxn]; struct data { int l,r,w; }q[maxn]; int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } ll ksm(ll x,int y) { ll res=1; for(;y;y>>=1,x=x*x%mod) if(y&1)res=res*x%mod; return res; } void cal(int W) { num=0; for(int i=1;i<=n;i++) { if(a[i]==W) { t[++num]=i; L[num]=0; memset(f[num],0,sizeof(f[num])); } } for(int i=1;i<=m;i++) { if(q[i].w==W) { if(!num){ans=-1;return;} int l=lower_bound(t+1,t+num+1,q[i].l)-t; int r=lower_bound(t+1,t+num+1,q[i].r)-t-1; L[r]=max(L[r],l); } } f[0][0]=1; for(int i=1;i<=num;i++) { ll v1=ksm(W,p[t[i]+1]-p[t[i]]); ll v2=ksm(W-1,p[t[i]+1]-p[t[i]]); for(int j=0;j<i;j++)if(f[i-1][j]) { if(j>=L[i])f[i][j]=(f[i][j]+f[i-1][j]*v2)%mod; f[i][i]=(f[i][i]+f[i-1][j]*(v1+mod-v2))%mod; } } ll res=0; for(int i=0;i<=num;i++)res=(res+f[num][i])%mod; ans=ans*res%mod; } void solve() { n=read(),m=read(),A=read(); mx=num=0; for(int i=1;i<=m;i++) { q[i].l=read(),q[i].r=read()+1,q[i].w=read(); p[++num]=q[i].l,p[++num]=q[i].r,w[++mx]=q[i].w; } p[++num]=1,p[++num]=n+1; sort(p+1,p+num+1); n=unique(p+1,p+num+1)-p-1; sort(w+1,w+mx+1),mx=unique(w+1,w+mx+1)-w-1; for(int i=1;i<=n;i++)a[i]=inf; for(int i=1;i<=m;i++) { q[i].l=lower_bound(p+1,p+n+1,q[i].l)-p; q[i].r=lower_bound(p+1,p+n+1,q[i].r)-p; for(int j=q[i].l;j<q[i].r;j++)a[j]=min(a[j],q[i].w); } ans=1; for(int i=1;i<=mx;i++) { cal(w[i]); if(ans==-1) { puts("0"); return; } } for(int i=1;i<n;i++) { if(a[i]==inf) ans=ans*ksm(A,p[i+1]-p[i])%mod; } cout<<ans<<'\n'; } int main() { for(int T=read();T;T--)solve(); return 0; }

T2 ことりのおやつ

跳过第一题之后发现这道题巨良心QwQ 贼开心咦嘻嘻 读题写代码系列

一个简单的spfa另外注意细节：特判终点（即使困住又能怎样，到达就好了） #include<cstdio> #include<cstring> #include<iostream> #include<cstdlib> #include<vector> #include<queue> #include<stack> #include<algorithm> #include<deque> #include<cmath> #include<cctype> #define LL long long #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; const int maxn=4000000+5; const int inf=0x3f3f3f3f; int tot=0; LL n,m,g,q,s,t; int head[maxn],vis[maxn]; LL limit[maxn],dist[maxn]; struct edge { int start,end; LL value; }e[maxn<<1]; int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } void init() { tot=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,LL w) { e[tot].end=v; e[tot].value=w; e[tot].start=head[u]; head[u]=tot++; } void spfa() { memset(vis,0,sizeof(vis)); memset(dist,inf,sizeof(dist)); queue<int >que; que.push(s); dist[s]=0; vis[s]=1; while(!que.empty()) { int u=que.front(); que.pop(); vis[u]=0; for(int i=head[u];~i;i=e[i].start) { int v=e[i].end; LL w=e[i].value; if((dist[u]+w<dist[v]&&dist[u]*q+w*q<=limit[v]) || (dist[u]+w<dist[v]&&v==t)) { dist[v]=dist[u]+w; if(!vis[v]) { vis[v]=1; que.push(v); } } } } if(dist[t]<=g) printf("%lld\n",dist[t]); else printf("wtnap wa kotori no oyatsu desu!\n"); } void readdata() { scanf("%lld%lld%lld%lld%lld%lld",&n,&m,&s,&t,&g,&q); for(int i=1;i<=n;i++) { LL hi,li; scanf("%lld%lld",&hi,&li); limit[i]=li-hi; } for(int i=1;i<=m;i++) { LL w; int u=read(),v=read(); scanf("%lld",&w); addedge(u,v,w); addedge(v,u,w); } } int main() { init(); readdata(); spfa(); return 0; }

一百昏~

T3 诗歌

题目描述 小 F 是一个爱写诗的小姑娘。

“我能看一看你写的诗吗？”

“看吧，别念出来哦，我会害羞的。”

小 F 慵懒地坐在午后的阳光下，她在写诗，可是似乎没有什么灵感。

她用手指勾勒着远方绵延的山，就写关于远方的诗吧。

远方的山总共有 N 个山峰，从左往右第 i 个山峰有一个高度Hi。小 F 认为一个三元组 (i,j,k) 可以写成一首诗，当且仅当1≤i<j<k≤N 且Hi−Hj=Hj−Hk。

小 F 和大 F 生活的国家—— Fairy 国地形十分奇特，保证 H1…N一定是一个 1…N 的排列。

小 F 想写诗给大 F 看，但是不知道自己能不能写成，于是她想问问你。

输入格式

第一行一个正整数 N ，表示山峰的数量。

第二行 N 个正整数 H1…N，表示从左往右每座山峰的高度，保证是个1…N 的排列。

输出格式

一行一个字符串 YES 或 NO ，表示小 F 能否写出一首诗，即是否存在三元组 (i,j,k) 满足1≤i<j<k≤N 且Hi−Hj=Hj−Hk 。

---

题目很简单…… 拿着就想搞暴力； but看一眼数据范围: $3\le N\le 3\times 10^5$ 欧耐斯，能骗个四五十分吧？ 心想四五十分也是分，于是就开开心心用了两分钟写了个暴力 写完后开始怀疑人生：这道题是只输出“YES”“NO”吧？只输出就得有五十分了吧？ 于是在暴力中加了个特判：if n>100000 printf(“YES\n”); 被自己的机智折服orz最后拿了68昏，感动QAQ 蓝鹅考试结束后经过实测，如果>100000后输出“NO”会有75 otz 扯淡结束……

正解是树状数组或者线段树，鉴于对线段树的深通恶绝，最后写了树状数组; 做法十分巧妙，考场想不到系列嘤嘤嘤 #include<cstdio> #include<cstring> #include<iostream> #include<cstdlib> #include<vector> #include<queue> #include<stack> #include<algorithm> #include<deque> #include<cmath> #include<cctype> #define LL long long #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; const int maxn=300000+5; int n,m; int a[maxn]; int tree[maxn<<1]; int read() { char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } struct TRAR { int lowbit(int x) { return x & (-x); } void add(int x,int value) { for(int i=x;i<=n;i+=lowbit(i)) { tree[i]+=value; } } int getsum(int x) { int sum=0; for(int i=x;i>0;i-=lowbit(i)) { sum+=tree[i]; } return sum; } }T; int main() { n=read(); for(int i=1;i<=n;i++) { a[i]=read(); } for(int i=1;i<=n;i++) { int l=max(1,2*a[i]-n); int r=min(n,2*a[i]-1); int ans=T.getsum(r)-T.getsum(l-1); if(ans&1) { printf("YES\n"); return 0; } T.add(a[i],1); } printf("NO\n"); return 0; }

老师给的标程是线段树+hash，看了一眼太长就扔一边了QAQ

总结

老师说是noip的水平，看了一眼自己的分数…… 好吧蒟蒻就是我 第一名的巨佬把第一题做出来了%%%%%%