#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<string>#include<vector>#include<stack>#include<bitset>#include<cstdlib>#include<cmath>#include<set>#include<list>#include<deque>#include<map>#include<queue>#include<unordered_map>#include<unordered_set>usingnamespace std;typedeflonglong ll;constint INF =0x7fffffff;constdouble eps =1e-8;int x, y, n;chars[200005];intsx[200005],sy[200005];intmain(int argc,constchar*argv[]){freopen("input.in","r", stdin);scanf("%d%s%d%d",&n, s +1,&x,&y);if (abs(x) +abs(y) > n || (n + x + y) &1) { cout <<-1<< endl;return0; }for (int i =1; i <= n; i++) {sx[i] =sx[i -1];sy[i] =sy[i -1];if (s[i] =='R') {sx[i]++; }elseif (s[i] =='L') {sx[i]--; }elseif (s[i] =='U') {sy[i]++; }else {sy[i]--; } }int res =2e5;for (int i =0, j =0; i <= n; i++) {while (j <= n &&abs(sx[i] +sx[n] -sx[j] - x) +abs(sy[i] +sy[n] -sy[j] - y) > j - i) j++;if (j <= n) res =min(res, j - i);elsebreak; } cout << res << endl;return0;}
D. Berland Fair
去环形集市买东西,看到可以买就直接付钱去下一个,直到没钱为止。求消费的次数。
Intuition
求出一次环形逛集市消耗了多少,然后取余减少重复的次数。
Solution
#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<string>#include<vector>#include<stack>#include<bitset>#include<cstdlib>#include<cmath>#include<set>#include<list>#include<deque>#include<map>#include<queue>#include<unordered_map>#include<unordered_set>usingnamespace std;typedeflonglong ll;constint INF =0x7fffffff;constdouble eps =1e-8;int n;ll T;constint MAXN =2e5+5;inta[MAXN];intmain(int argc,constchar*argv[]){ // freopen("input.in", "r", stdin); cin >> n >> T;for (int i =1; i <= n; i++) {scanf("%d",&a[i]); } ll res =0;while (true) { ll t =0, m =0;for (int i =1; i <= n; i++) {if (T >= t +a[i]) { t +=a[i]; m++; } }if (!m) break; res += T / t * m; T %= t; } cout << res << endl;return0;}