【NOIP2012普及组】寻宝

mac2022-06-30  22

这道实际难度入门的题做得真™要麻烦死我,由于摸不到电脑,在大脑里调了3天都翻不转!!

P1076 寻宝

思路:暴力模拟(这是基础,单纯暴力据说会全部TLE)+取模优化(这样时间复杂度骤降到O(NM))。

AC代码:

#include<bits/stdc++.h> using namespace std; long long n,m,t,a[10005][105],able[10005],start,ans,p; bool sign[10005][105]; int main() { scanf("%lld%lld",&n,&m); for(long long i=1; i<=n; i++) for(long long j=0; j<m; j++) { scanf("%lld%lld",&t,&a[i][j]); sign[i][j]=t; if(sign[i][j])able[i]++; } scanf("%lld",&start); long long j=start; for(long long i=1; i<=n; i++) { ans+=a[i][start]; p=a[i][start]%able[i]; if(p==0)p=able[i]; while(1) { if(sign[i][j])p--; if(!p)break; j++; if(j==m)j=0; } start=j; } ans=ans%20123; printf("%lld",ans); return 0; } 真™不容易

核心优化:

p=a[i][start]
转载请注明原文地址: https://mac.8miu.com/read-60075.html
最新回复(0)