연결:
http://codeforces.com/contest/797/problem/E
제목:
a 배열, q 번 질문, 매번 p, k 를 드 립 니 다. 매번 조작 시 p = p + a [p] + k, p 가 n 보다 클 때 까지
총 몇 번 했 냐 고.
문제 풀이:
먼저 k 가 325 를 초과 하지 않 을 때의 답안 을 미리 처리 하고 k 가 325 보다 크 면 폭력 으로 계산한다.
코드:
1 #include
2 #include <set >
3 #include
4 #include
5 #include
6 #include
7 #include <string >
8 #include
9 #include
10 #include
11 #include
12 #include
13 #include
14 #include
15 using namespace std;
16 #define rep(i,a,n) for (int i=a;i17 #define per(i,a,n) for (int i=n-1;i>=a;i--)
18 #define all(x) (x).begin(),(x).end()
19 #define pb push_back
20 #define mp make_pair
21 #define lson l,m,rt<<1
22 #define rson m+1,r,rt<<1|1
23 typedef long long ll;
24 typedef vector<int > VI;
25 typedef pair<int , int > PII;
26 const ll MOD = 1e9 + 7 ;
27 const int INF = 0x3f3f3f3f ;
28 const int MAXN = 1e5 + 7 ;
29 // head
30
31 const int BLK = 325 ;
32 int a[MAXN], dp[BLK][MAXN];
33
34 int main() {
35 ios::sync_with_stdio(false );
36 int n;
37 cin >> n;
38 rep(i, 1 , n + 1 ) cin >> a[i];
39 rep(k, 1 , BLK) per(p, 1 , n + 1 ) {
40 int q = p + a[p] + k;
41 if (q > n) dp[k][p] = 1 ;
42 else dp[k][p] = dp[k][q] + 1 ;
43 }
44 int q;
45 cin >> q;
46 while (q--) {
47 int p, k;
48 cin >> p >> k;
49 if (k < BLK) cout << dp[k][p] << endl;
50 else {
51 int sum = 0 ;
52 while (p <= n) p = p + a[p] + k, sum++;
53 cout << sum << endl;
54 }
55 }
56 return 0 ;
57 }
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSON
JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다.
그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다.
저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
