这道实际难度入门的题做得真™要麻烦死我,由于摸不到电脑,在大脑里调了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]