A
做法：模拟
这里给的计算器操作都是可逆的。那么只要注意中间会爆longlong用int128存就好，比赛的时候因为这个东西爆了两发...
#include <bits/stdc++.h>
using namespace std;
namespace io {
#define in(a) a=read()
#define out(a) write(a)
#define outn(a) out(a),putchar('\n')
#define I_int __int128
inline I_int read() {
I_int x = 0 , f = 1 ; char c = getchar() ;
while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; }
while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; }
return x * f ;
}
char F[ 200 ] ;
inline void write( I_int x ) {
if( x == 0 ) { putchar( '0' ) ; return ; }
I_int tmp = x > 0 ? x : -x ;
if( x < 0 ) putchar( '-' ) ;
int cnt = 0 ;
while( tmp > 0 ) {
F[ cnt ++ ] = tmp % 10 + '0' ;
tmp /= 10 ;
}
while( cnt > 0 ) putchar( F[ -- cnt ] ) ;
}
#undef I_int
}
using namespace io ;
#define N 110
#define ll __int128
int n;
ll x;
ll opt[N];
ll a[N];
int main() {
scanf("%d", &n);
x = read();
for(int i = 1; i <= n; ++i) {
opt[i] = read(), a[i] = read();
}
for(int i = n; i; i--) {
if(opt[i] == 1) x = (__int128)(x - a[i]);
if(opt[i] == 2) x = (ll)(x + a[i]);
if(opt[i] == 3) x = (ll)(x / a[i]);
if(opt[i] == 4) x = (ll)(x * a[i]);
}
outn(x);
return 0;
}B
做法：贪心
猜的结论是0后面能放4就优先放4,4后面能优先放0就放0,2后面能优先放0就放0，这样就过了，貌似和标算做法不一样，不过应该是对的。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100010
ll ans = 0;
int n, a[N], cnt[5], f[N];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]), cnt[a[i]]++;
for(int i = 1; i <= n; ++i) {
if(f[i - 1] == 0) {
if(cnt[4]) cnt[4]--, ans += 16, f[i] = 4;
else if(cnt[2]) cnt[2]--, ans += 4, f[i] = 2;
else if(cnt[0]) cnt[0]--, f[i] = 0;
continue;
}
if(f[i - 1] == 2) {
if(cnt[0]) cnt[0]--, ans += 4, f[i] = 0;
else if(cnt[4]) cnt[4]--, ans += 4, f[i] = 4;
else if(cnt[2]) cnt[2]--, f[i] = 2;
continue;
}
if(f[i - 1] == 4) {
if(cnt[0]) cnt[0]--, ans += 16, f[i] = 0;
else if(cnt[2]) cnt[2]--, ans += 4, f[i] = 2;
else if(cnt[4]) cnt[4]--, f[i] = 4;
}
}
printf("%lld\n", ans);
return 0;
}C
做法：dp
赛时想了一个dp然后自行hack掉了于是写D去了。
赛后发现数据太水这个明显错误的dp也可以过。
果然我dp还是菜，完全没想到正解。
将原序列排序一遍，那么每个数可以转移的区间就是以它为起点的后缀，设\(f[i][j]\)表示当前在点i，耐久度为j是否可行，分为走这里和不走这里两种情况转移（注意如果前后两个点价值相同那肯定不走），然后类似01背包那样子转移。
注意dp数组要第二维要开大一点（至少要大于6000，实际多大并不知道因为我开了10010就直接过了，请自行尝试适合的大小），然后用bool存
#include <bits/stdc++.h>
using namespace std;
bool f[3010][10010];
int n;
struct Node {
int id, val;
}a[3010];
bool cmp(Node a, Node b) { return a.val > b.val; }
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i].val), a[i].id = i;
sort(a + 1, a + n + 1, cmp);
int l;
for(int i = 1; i <= n; ++i)
if(a[i].id == 1) {
l = i;
f[i][a[i].val] = 1;
break;
}
for(int i = l + 1; i <= n; ++i) {
if(a[i].id == n) {
l = i;
for(int j = 6010; j >= 0; --j) f[i][j] |= f[i - 1][j ^ a[i].val];
break;
}
if(a[i].val == a[i - 1].val) {
for(int j = 0; j <= 6010; ++j) f[i][j] |= f[i - 1][j];
} else {
for(int j = 0; j <= 6010; ++j) f[i][j] |= f[i - 1][j], f[i][j] |= f[i - 1][j ^ a[i].val];
}
}
for(int i = 6010; i; --i)
if(f[l][i]) return printf("%d\n", i), 0;
puts("-1");
}D
做法：欧拉函数
用容斥也是可以算的但是不会。（一位大佬：这不是入门容斥吗）
由\(gcd(x,n)=gcd(n-x,n)\)可知与n互质的数一定是成对出现的，而且两人从两端走所以x和n-x一定同时走到...（赛时就没想到这个），每对互质的数一共会给两人分别带来\(k^{n}\)的收益。也就是说每个人的总收益是\(k^{\frac{\phi(n)}{2}*n}\)（与n互质的数的和为\(\frac{\phi(n)}{2}*n\)），于是直接这样算出来这个值然后乘A+B就行了。比赛时没想到x和n-x一定同时走到于是暴力处理出来每个和它互质的数然后直接算...
其实就是把公式展开了而已，不过也有90分。
关于上面的公式的证明，可以戳这里
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 3162278
const ll mod = 1e9 + 7;
ll n, k, A, B, cnt = 0;
ll power(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
int main() {
scanf("%lld%lld%lld%lld", &n, &k, &A, &B);
ll m = n, phi = n;
for(ll i = 2; i * i <= m; ++i) {
if(m % i == 0) {
while(m % i == 0) m /= i;
phi = phi / i * (i - 1);
}
if(m == 1) break;
}
if(m > 1) phi = phi / m * (m - 1);
printf("%lld\n", ((A + B) % mod) * (power(k % mod, phi / 2 * n) % mod) % mod);
}90分暴力
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 5000100
const ll mod = 1e9 + 7;
ll n, k, A, B, cnt = 0;
ll a[N];
ll power(ll a, ll b) {
ll ans = 1;
while(b) {
if(b & 1) ans = (__int128)ans * a % mod;
a = (__int128)a * a % mod;
b >>= 1;
}
return ans;
}
ll gcd(ll a, ll b) {
if(!b) return a;
return gcd(b, a % b);
}
int main() {
scanf("%lld%lld%lld%lld", &n, &k, &A, &B);
//ll phi = mod - 1;
cnt = 0;
for(ll i = 1; i <= n; ++i)
if(gcd(n, i) == 1) {
a[++cnt] = i;
// a[++cnt] = n - i;
// if(cnt > (int)(1e6)) while(1) puts("233");
}
ll a1 = 1, b1 = 1; k %= mod;
for(ll i = 1; i <= cnt; ++i) {
a1 = (__int128)a1 * power(k, a[i]) % mod;
// a1 = (__int128)a1 * power(k, n - a[i]) % mod;
// b1 = (__int128)b1 * power(k, a[i]) % mod;
b1 = (__int128)b1 * power(k, n - a[i]) % mod;
}
A %= mod; B %= mod;
A = (__int128)A * a1 % mod; B = (__int128)B * a1 % mod;
printf("%lld\n", (A % mod + B % mod) % mod);
}G
做法：模拟
主要是要注意两点，首先这个序列是个排列（所以它不会有重复数字出现），于是由这个我们可以推出一个显然的结论就是\(r-l=max_{[l,r]}-min_{[l,r]}\)时这是个连续区间。
然后我们处理出每个数字出现的位置，于是可以求出第一个可能满足题目要求的区间，记为\([ql,qr]\)，并保存这个区间的最大最小值。
（为什么是可能呢？因为你现在只求出了x到y之间的数所需要的最短的区间，但是你并不知道这个区间里有没有其他不应该有的数字，让这个区间变得真正合法，就是我们下面要做的事情）
设每个数出现的位置为\(pos\)。
我们可以将原始区间记为\([l,r]\)(即一开始的\([pos[x],pos[y]]\))。
尝试不断拓展这个区间\([l,r]\)，在拓展过程中如果出现了大于最大值，或者小于最小值的，就用一开始处理\([ql,qr]\)的方法更新\([ql,qr]\)。直至两区间重合。那么此时的\([l,r]\)即为答案了。
这样做是\(O(n)\)的，不过常数可能稍大，因为会有重复访问。
写了RMQ的话就可以稳定\(O(n)\)了（不过预处理要\(O(nlogn)\)，所以大概实际效率上是没什么大的区别的）
#include <bits/stdc++.h>
using namespace std;
#define N 100010
int a[N], pos[N];
int n, x, y;
int main() {
scanf("%d%d%d", &n, &x, &y);
for(int i = 1; i <= n; ++i)
scanf("%d", &a[i]), pos[a[i]] = i;
int l = pos[x], r = pos[y];
if(l > r) swap(l, r);
/*答案至少要包含区间[l, r]不然不会包含x和y*/
int mx = 0, mn = N;
for(int i = l; i <= r; ++i) {
mx = max(mx, a[i]);
mn = min(mn, a[i]);
}
int ql = N, qr = 0;
for(int i = mn; i <= mx; ++i) {
ql = min(ql, pos[i]);
qr = max(qr, pos[i]);
}
/*[ql, qr]其实就是目前已知的最小的可能满足题目要求的区间，随着答案[l, r]的扩大[ql, qr]也在更新*/
/*主要思路就是让区间[l, r]向区间[ql, qr]逼近直至重合*/
while(ql != l || qr != r) {
while(ql != l) {
int t = a[--l];
while(mx < t) {
ql = min(pos[++mx], ql);
qr = max(pos[mx], qr);
}
while(mn > t) {
ql = min(pos[--mn], ql);
qr = max(pos[mn], qr);
}
}
while(qr != r) {
int t = a[++r];
while(mx < t) {
ql = min(pos[++mx], ql);
qr = max(pos[mx], qr);
}
while(mn > t) {
ql = min(pos[--mn], ql);
qr = max(pos[mn], qr);
}
}
}
printf("%d %d\n", l, r);
}其他题不会了。我好菜啊。
官方题解戳这里
提取码是k8xd
京公网安备 11010502036488号