[题解]oi普及周赛13
[普及组]牛客普及周赛13题解
T1 zn的手环
大讨论一下就好了 先转化成24h制, 然后算一下时间跨度也可以。 具体如下: 1.如果同为早上或者下午, 入睡时间早于起床时间那么答案可以直接算。 否则需要把起床时间+24h来算 2.如果不同的话, 此时我们对起床时间直接+12h即可。
T2 zn的游戏
直接找最接近的两个数之间的距离就行了, 在这里两个数指max{ai}和min{ai}, 然后对距离取min即可 为什么呢...因为如果[l, r]中有子区间[l', r']满足[l', r']包含了最小值和最大值, 那么肯定不选[l, r]。 同理我们发现每一对最大值和最小值都能组成一个区间, 然后我们只需要取最接近的一组就行了。 由于读入量过大所以需要快读, 不然会tle最后一个点。
T3 zn的绳子
很容易可以发现, 上一个位置有没有交叉对下一个位置并没有什么影响。 然后我们可以发现最多有n - 1个交叉, 最少有0个交叉 那么我们需要<=k个交叉的话, 只需要在n - 1个交叉中选k个来放, 也就是C(n - 1, k) 然后对于n 最多为1e7 那么我们需要线性求逆元的姿势。 可以先logN算出inv(n!) 然后通过inv(i!) = inv((i + 1)!) * (i + 1) 来倒推
T4 zn的幸运数字
首先, 对于质数P有这么一个性质
对于任意整数x满足都有
很容易可以证明
首先对于p, 由于a为整数, 所以有Ap >= Ax 然后对于质数p, d(p) = 2, 由于2 ~ p内的整数都满足d(x) >= 2 所以有Bd(p) <= Bd(x) 所以Ap - Bd(p) >= Ax - Bd(x)
所以我们只需要从n往下扫到第一个质数就可以停下来了。
由于质数密度很大, 在随机数据下(好像不随机数据也可以), 每logN就会出现一个质数
所以期望效率是的
但是对于x = 1的时候, 考虑到, 此时并不满足对于任意A, B有
所以我们需要特判一下x = 1时候的情况。
吐槽
QAQ怎么好像没啥人打((( 好像没啥人答疑(对比上一场是不是我语文变好了, 果然文化课快乐(迫真)) 好像T2因为数据过大的原因把scanf卡了, 要快读才能过最后一个点
Code
//T1 #include<bits/stdc++.h> using namespace std; #define ll long long inline ll read() { ll x = 0, f = 1; char ch = getchar(); for(; ch < '0' || ch>'9'; ch = getchar()) if(ch == '-') f = -f; for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; return x * f; } inline void chkmin( int &a, int b ) { if(a > b) a = b; } inline void chkmax( int &a, int b ) { if(a < b) a = b; } #define _ read() #define ln endl int main() { string s1, s2; int h1 = _, m1 = _; cin >> s1; int h2 = _, m2 = _; cin >> s2; if(s1 != s2) h2 += 12; else if(h2 < h1 || h1 == h2 && m1 > m2 ) h2 += 24; int h3 = _, m3 = _; if(m1 > m2) m2 = m2 + 60, --h2; int h4 = h2 - h1, m4 = m2 - m1; if(h4 == h3 && m3 == m4) return puts("YES"), 0; puts("NO"); cout << h4 << "h" << m4 << "min" << ln; // cout << h2 - h1 << "h" << m2 - m1 << "min" << ln; }
//T2 #include<bits/stdc++.h> using namespace std; #define ll long long inline ll read() { ll x = 0, f = 1; char ch = getchar(); for(; ch < '0' || ch>'9'; ch = getchar()) if(ch == '-') f = -f; for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; return x * f; } inline void chkmin( int &a, int b ) { if(a > b) a = b; } inline void chkmax( int &a, int b ) { if(a < b) a = b; } #define _ read() #define ln endl int a[10000007]; int pos1, pos2, ans; int main() { int n = _; int mx = 0, mn = 2e9; ans = 2e9; for( int i = 1; i <= n; i++ ) a[i] = _, mx = max(mx, a[i]), mn = min(mn, a[i]); for( int i = 1; i <= n; i++ ) { if(mx == a[i]) pos2 = i; if(mn == a[i]) pos1 = i; if(pos1 && pos2) ans = min(abs(pos2 - pos1) + 1, ans); } cout << ans << ln; }
//T3 #include<bits/stdc++.h> using namespace std; #define ll long long inline ll read() { ll x = 0, f = 1; char ch = getchar(); for(; ch < '0' || ch>'9'; ch = getchar()) if(ch == '-') f = -f; for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; return x * f; } inline void chkmin( int &a, int b ) { if(a > b) a = b; } inline void chkmax( int &a, int b ) { if(a < b) a = b; } #define _ read() #define ln endl const int mod = 1e9 + 7; const int N = 1e7 + 7; int n, k, fac[N], inv[N], ans; inline int power( int a, int b ) { int tmp = 1; while(b) { if(b & 1) tmp = 1ll * tmp * a % mod; b >>= 1; a = 1ll * a * a % mod; } return tmp; } inline int C( int a, int b ) { return 1ll * fac[a] * inv[b] % mod * inv[a - b] % mod; } int main() { n = _; k = _; --n; fac[0] = 1; for( int i = 1; i <= n; i++ ) fac[i] = 1ll * fac[i - 1] * i % mod; inv[n] = power(fac[n], mod - 2); for( int i = n - 1; i >= 0; i-- ) inv[i] = 1ll * inv[i + 1] * (i + 1) % mod; for( int i = 0; i <= min(k, n); i++ ) ans = ( ans + C(n, i) ) % mod; cout << ans << ln; }
//T3 #include<bits/stdc++.h> using namespace std; #define ll long long inline ll read() { ll x = 0, f = 1; char ch = getchar(); for(; ch < '0' || ch>'9'; ch = getchar()) if(ch == '-') f = -f; for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0'; return x * f; } inline void chkmin( int &a, int b ) { if(a > b) a = b; } inline void chkmax( int &a, int b ) { if(a < b) a = b; } #define _ read() #define ln endl ll a, b, r, ans, tmp; inline bool prime( ll x ) { for(ll i = 2; i * i <= x; i++ ) if(x % i == 0 ) return 0; return 1; } inline ll solve( ll x ) { ll tmp = 0; for( ll i = 1; i * i <= x; i++ ) if(x % i == 0) { ++tmp; if(i * i == x); else ++tmp; } return tmp; } int main() { a = _, b = _, r = _; ans = -2e18; while(r) { ll d = solve(r); if(a * r - b * d > ans) tmp = r, ans = a * r - b * d; // cout << r << " " << a * r + b * d << ln; if(prime(r)) break; --r; } if(a - b > ans) tmp = 1; // cout << ans << ln; // cout << r << ln; cout << tmp << ln; }