德阳建设局网站,苏州集团网站设计定制,阿里云网页版入口,短链生成网站文章目录 A题目AC Code#xff1a; B题目AC Code#xff1a; C题目AC Code#xff1a; D题目你以为这就完了#xff1f; 时间复杂度分析#xff1a;AC Code#xff1a; E A
题目
这个没什么好说的#xff0c;就先输出一个 1#xff0c;再输出 n n n 个 01就大功告成… 文章目录 A题目AC Code B题目AC Code C题目AC Code D题目你以为这就完了 时间复杂度分析AC Code E A
题目
这个没什么好说的就先输出一个 1再输出 n n n 个 01就大功告成了。
AC Code
#include algorithm
#include iostream
#include cstring
#include vector
#include queue
#include stack
#include cmath
#include list
#include set
#include map
using namespace std;
int n;int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin n;cout 1;for (int i 1; i n; i ) cout 01;return 0;
}B
题目
要获取更多 x x x 国货币只能用 x − 1 x - 1 x−1 国货币换。 所以我们可以从 1 1 1 国一直换到 n n n 国输出结束。
AC Code
#include algorithm
#include iostream
#include cstring
#include vector
#include queue
#include stack
#include cmath
#include list
#include set
#include map
using namespace std;
int n;
long long a[200100];
int s[200100], t[200100];int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin n;for (int i 1; i n; i ) cin a[i];for (int i 1; i n; i ) cin s[i] t[i];for (int i 1; i n; i ) {a[i 1] t[i] * (a[i] / s[i]);}cout a[n];return 0;
}C
题目
你会发现 50 0 3 2 ⋅ 1 0 8 500^32\cdot10^8 50032⋅108所以可以暴力枚举高桥所在的位置如果他行进的过程中没有经过海洋就将答案加一。如果经过海洋了就直接枚举下一个点。
AC Code
#include algorithm
#include iostream
#include cstring
#include vector
#include queue
#include stack
#include cmath
#include list
#include set
#include map
using namespace std;
int h, w, n;
char m[510][510];
string s;
mapchar, int dir;
int dx[4] {0, 0, -1, 1}, dy[4] {-1, 1, 0, 0};
int ans;
bool check(int x, int y) {for (int i 0; i n; i ) {int nx x dx[dir[s[i]]], ny y dy[dir[s[i]]];if (nx 0 nx h ny 0 ny w m[nx][ny] .) {x nx;y ny;}else return 0;}return 1;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin h w n;cin s;for (int i 1; i h; i ) {for (int j 1; j w; j ) cin m[i][j];}dir[L] 0, dir[R] 1, dir[U] 2, dir[D] 3;for (int i 1; i h; i ) {for (int j 1; j w; j ) {if (m[i][j] .) {ans check(i, j);}}}cout ans;return 0;
}D
题目
这个题并不难但是细节很多仔细看我因为一些零碎的细节卡了 40min
首先我们先讨论那些“有规律”的部分。我们发现对于两个数 n n n 和 m m m在 n m nm nm 范围内有 n m − 2 × gcd ( n , m ) n m - 2\times\gcd(n, m) nm−2×gcd(n,m) 个数满足只被 n n n 和 m m m 中的一个数字整除。
这个结论怎么来的呢
首先对于可以被 n n n 整除的一共有 n m n \frac{nm}{n} nnm 共 m m m 个可以被 m m m 整除的一共有 n m m \frac{nm}{m} mnm 共 n n n 个。
那么 − 2 × gcd ( n , m ) -2\times\gcd(n, m) −2×gcd(n,m) 又是怎么来的呢
首先 n m nm nm 范围内有 n m n m gcd ( n , m ) \frac{nm}{\frac{nm}{\gcd(n, m)}} gcd(n,m)nmnm 个数即 gcd ( n , m ) \gcd(n,m) gcd(n,m) 个数可以被 n n n 和 m m m 整除。我们要在可以被 n n n 整除的部分减去它还要在可以被 m m m 整除的部分减去它。所以是 − 2 × gcd ( n , m ) -2\times\gcd(n,m) −2×gcd(n,m)。
然后我们就可以将答案直接跳到 n m ( k / ( n m − 2 gcd ( n , m ) ) ) nm(k/(n m - 2\gcd(n, m))) nm(k/(nm−2gcd(n,m)))此时 k k k 变成 k m o d ( n m − 2 gcd ( n , m ) ) k \mod (n m - 2\gcd(n, m)) kmod(nm−2gcd(n,m))。
我们继续讨论可以枚举用 k 1 k1 k1 和 k 2 k2 k2 两个变量依次跳到答案。如果 k 1 k1 k1 跳的远就跳 k 2 k2 k2否则跳 k 1 k1 k1。如果两个跳的一样远就都跳依次这两次不算在跳的次数内。一共跳 k k k 次后较大的就是满足条件的加到答案上即可。
你以为这就完了
如果减掉前面“有规律”的部分后发现 k k k 等于 0 0 0 时不加任何特判会输出一个 n m nm nm 的倍数的数。但是我们要的是最大的比上述不合法答案小的答案。此时如果我们把 k k k 设为 n m − 2 gcd ( n , m ) nm-2\gcd(n, m) nm−2gcd(n,m)答案减去 n m nm nm 就可以解决这个问题。
还有一个很重要的东西long long
时间复杂度分析
按最坏情况来说 gcd ( n , m ) 1 \gcd(n, m)1 gcd(n,m)1此时时间复杂度就是 n m nm nm而且跑不到这么多所以执行次数不会超过 2 ⋅ 1 0 8 2\cdot10^8 2⋅108合格。
AC Code
#include algorithm
#include iostream
#include cstring
#include vector
#include queue
#include stack
#include cmath
#include list
#include set
#include map
using namespace std;
long long n, m, k;
long long gcd(long long x, long long y) {return x % y 0ll ? y : gcd(y, x % y);
}
long long ans;
long long cnt;
long long cnt1;
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin n m k;long long g gcd(n, m);ans n * m * (k / (n m - g * 2));k k % (n m - g * 2);if (k 0) {ans - n * m;k n m - g * 2;}long long k1 0ll, k2 0ll;cnt1 0ll;for (long long i 1; i k; i ) {if (k1 n k2 m) {k1 n;}else if (k1 n k2 m) {k2 m;}else {k1 n;k2 m;i--;}}ans max(k1, k2);cout ans;return 0;
}E
什么不是 A-D题解吗怎么还有 E
我才不会给出详细的解法的我只给一个小小的提示懒标线段树
