A. 完全 k 叉树
若想找到最长的一条路径,不妨找出两个离根最远,且没有公共路径的点。假设树共有 m 层,那么左下角的点到根的距离是 m-1,且这个点一定一个足够远的点。如果最后一层的点的数量大于倒数第二层的点数,则可以取最后一层的最右边的点作为计算最大距离的点,它到根的距离为 m-1。否则取倒数第二层最右边的点作为计算最大距离的点,它到根的距离为 m-2。(取点方法不唯一)由于没有公共路径,所以直接把这两个点到根的距离相加即可。
标程的这种写法中还会有一种情况是最后一层点数为 0,则左下角和右下角的点到根的距离都为 m-2。(当然你可以采取其他方法免除这种情况)
注意 k=1 的 text,此时应当输出 n-1。(如果不特判,在计算树的层数时可能会超时)
时间复杂度O(log𝑘 𝑛)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ll n, k, cnt = 0, now = 1, t;
cin >> t;
while(t--){
cnt = 0, now = 1;
cin >> k >> n;
if(k == 1){
cout << n-1 << "\n";
continue;
}
while(n > 0) {
n -= now;
now *= k;
cnt++;
if(n < now) break;
}
if(n == 0) cout << cnt * 2 - 2 << endl;
else if(n <= now / k) cout << cnt * 2 - 1 << endl;
else cout << cnt * 2 << endl;
}
}
B. 距离产生美
签到题,首先我们比较当前位置和上一位置的数字,如果距离过近,就需要改变数字。用贪心的思想发现,把当前位置的数字改成一个很大的值,确保它和相邻的两个数字的距离都足够大,这样的方案是最优的。(因为可以修改的值域是1018,所以一定能找出这样的数字)然后再往后扫描即可。扫描一遍之后就可以输出答案了。
时间复杂度O(n)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
ll co[maxn];
int main(){
ll n, m, ans = 0;
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> co[i];
}
for(int i = 2; i <= n; i++)
if(abs(co[i] - co[i-1]) < m)
ans++, i++;
cout << ans;
}
C. 烤面包片
首先根据范围可得 4!!一定大于109(事实上甚至大于1018),所以 4!!!一定能被 mod 整除(n>4 也同理)。那么我们只需要判断 n≤3的情况了。直接计算即可。如果写一个阶乘函数,然后调用连续三次来获得答案,如:((n!%mod)!%mod)!%mod 可能会无法通过以下的 text:
2 2
(本应输出 0,但三次调用阶乘函数最终会输出 1,因为第一次调用得到 0,之后再调用阶乘函数发现 0!是 1)一个较好的处理方式是将 n=0,1,2 特判掉,然后预先计算出 3!!为720,然后用一次 for 循环解决这道题。
#include <bits/stdc++.h>
using namespace std;
int main(){
long long n, mod, now = 1;
cin >> n >> mod;
if(n == 0) return cout << 1 % mod, 0;
if(n < 3) return cout << n % mod, 0;
if(n > 3) return cout << 0, 0;
for(int i = 1; i <= 720; i++)
now = now * i % mod;
cout << now % mod;
}
D. 茶颜悦色
由题设 k 为正方形边长。首先我们可以通过确定正方形的底边来确定正方形。比如底边是由[x, y],[x + k, y]两点连成的边,那么这样的底边可以确定一个由[x, y],[x + k, y],[x, y + k],[x + k, y + k]四个点组成的正方形。假设我们用左下角的点[x, y]来代表这个正方形(下同)。现在我们来考虑某个点(a,b)可以被怎样的正方形包含。那么我们会发现,左下角的点的 x 坐标满足(a − k ≤ x ≤ a)且 y 坐标满足(b − k ≤ y ≤ b)会包含(a,b)这个点。
我们不妨用扫描线的思想来解决这道题。我们从左到右地扫描 x坐标,并用线段树维护当前 y 坐标上的点数量。即当目前扫描到区间[a − k, a]时,点(a,b)对 y 坐标为[b-k,b]中的正方形有贡献。所以当扫描到 a-k 时,将区间[b-k,b]全部+1。当扫描到 a 时,将区间对地-1。这样就可以描述(a,b)点对题目答案的贡献了。具体的做法:每个点(a,b)存两遍,一遍存(a-k,b)且置 flag 为 1,代表扫描到此点时要将区间+1,第二遍存(a,b)且置 flag 为-1,代表扫描到此点时要将区间-1。然后按 x 坐标排序,用线段树扫描 x 坐标即可。每次+1 之后区间查询全局最大值,更新答案。
时间复杂度O(𝑛log2 𝑛)
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
#define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
#define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
LL ma[SIZE],_tmp[SIZE];
void push(int id){
if(_tmp[id]==0)return;
_tmp[id*2]+=_tmp[id];
ma[id*2]+=_tmp[id];
_tmp[id*2+1]+=_tmp[id];
ma[id*2+1]+=_tmp[id];
_tmp[id]=0;
}
void pull(int id){
ma[id]=max(ma[id*2],ma[id*2+1]);
}
LL qq(int L,int R,int id,int ll,int rr){
if(R<ll||L>rr)return LLONG_MIN;
if(L>=ll&&R<=rr)return ma[id];
int mm=(L+R)/2;
push(id);
return max(qq(L,mm,id*2,ll,rr),qq(mm+1,R,id*2+1,ll,rr));
}
void ins(int L,int R,int id,int ll,int rr,LL v){
if(R<ll||L>rr)return;
if(L>=ll&&R<=rr){
ma[id]+=v;
_tmp[id]+=v;
return;
}
int mm=(L+R)/2;
push(id);
ins(L,mm,id*2,ll,rr,v);
ins(mm+1,R,id*2+1,ll,rr,v);
pull(id);
}
struct Data{
int x,y,ty;
Data(int x=0,int y=0,int ty=0):x(x),y(y),ty(ty){}
bool operator<(const Data& b)const{
return x<b.x||(x==b.x&&ty>b.ty);
}
}d[SIZE];
int dn;
VI yy;
int main(){
int n,k; R(n,k);
FOR(i,1,n){
int x,y;
R(x,y);
yy.PB(y-1);
yy.PB(y+k);
d[dn++]=Data(x,y,1);
d[dn++]=Data(x+k,y,-1);
}
SORT_UNIQUE(yy);
sort(d,d+dn);
LL an=0;
REP(i,dn){
int x=GET_POS(yy,d[i].y-1)+1;
int y=GET_POS(yy,d[i].y+k);
ins(0,SZ(yy)-1,1,x,y,d[i].ty);
LL res=qq(0,SZ(yy)-1,1,0,SZ(yy)-1);
//W(x,y,d[i].ty,res);
an=max(an,res);
}
W(an);
return 0;
}
E. 飞行棋
由题设骰子面数为 k,首先我们先来考虑当前到终点的距离 d 小于 k 的情况。只有当扔出的点数Q == d时,可以到达终点,概率为1/𝑘。否则都会到达一个新的点𝑑′,且𝑑′ < 𝑘,则相当于还是会有1𝑘的概率到达终点。每次掷骰子到达终点的概率均为1/𝑘,则此时的期望为 k。现在我们可以假设我们从终点出发,倒着做即可。假设现在到终点的距离为 n,那么只有可能从距离[n − k, n − 1]的区间掷骰子到此点,且概率均为1/𝑘,再加上投掷骰子的动作会使得期望+1。所以用概率 DP 的思想推得公式为
但是由于 n 过大,线性的递推是无法解决问题的,所以需要用矩阵快速幂优化计算过程来求解此题。
时间复杂度𝑂(𝑘³log₂𝑛)
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <list>
#include <cmath>
using namespace std;
#define mp make_pair
#define sz(a) a.size()
#define Se second
#define Fi first
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for(int i=0;i<(n);i++)
#define for1(i, n) for(int i=1;i<=(n);i++)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<long long > vl;
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int maxn = (int)200000+7;
const int me = 1;
const int fr = 10000000;
ll powmod(ll a,ll b) {ll res=1;a%=MOD; if(b<0) return -1; for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
#define mod(x) (((x)%MOD+MOD)%MOD)
int n=54;
struct mat{
ll m[55][55];
} unit;
mat operator *(mat a,mat b){
mat ret;
ll x;
forn(i,n)
forn(j,n){
x =0 ;
forn(k,n)
x+=mod((ll)a.m[i][k]*b.m[k][j]);
ret.m[i][j] = mod(x);
}
return ret;
}
void init_unit(){
forn(i,55)
unit.m[i][i]=1;
return ;
}
mat pow_mat(mat a,ll n){
mat ret = unit;
while(n){
if(n&1) ret = ret*a;
a = a * a;
n>>=1;
}
return ret;
}
int main() {
ll x;
init_unit();
mat t;
ll n,k;
int m;
cin>>n>>k;
ll p = powmod(k,MOD-2);
if(n <= k)
return cout<<k, 0;
mat tag;
forn(i,55) forn(j,55) tag.m[i][j] = 0;
for1(i,k) tag.m[i][3] = k;
tag.m[k+1][4] = 1;
forn(i,55) forn(j,55) t.m[i][j] = 0;
for1(i,k-1) t.m[i][i+1] = 1;
for1(i,k) t.m[k][i] = p;
t.m[k][k+1] = 1;
t.m[k+1][k+1] = 1;
mat res;
res = pow_mat(t,n - k);
res = res * tag;
x = res.m[k][5];
cout<<x<<endl;
}
F :三元组
对于一组满足条件的(i, j):
2 ∗ min(𝑎𝑖 + 𝑎𝑗, 𝑏𝑖 + 𝑏𝑗) ≤ max(𝑎𝑖 + 𝑎𝑗, 𝑏𝑖 + 𝑏𝑗)
也必然满足:
min(ai + aj, 𝑏𝑖 + 𝑏𝑗) ≤ max(𝑎𝑖 + 𝑎𝑗, 𝑏𝑖 + 𝑏𝑗)
不妨设 2(𝑎𝑖 + 𝑎𝑗) ≤ 𝑏𝑖 + 𝑏𝑗
,即ai + aj ≤ 𝑏𝑖 + 𝑏𝑗
此时,显然不需要考虑min(𝑎𝑖 + 𝑎𝑗, 𝑏𝑖 + 𝑏𝑗) = 𝑎𝑖 + 𝑎𝑗
这个条件
移项可得
(2 ∗ 𝑎𝑖 − bi) + (2 ∗ 𝑎𝑗 − bj) ≤ 0
直接按照2 ∗ 𝑎𝑖 − 𝑏𝑖
升序进行排序,记数组为P
此时可以发现性质:
若𝑃𝑖最多只能和𝑃𝑗匹配,则𝑃𝑖 + 1
只能和[i + 1, j]
之间的匹配
此时使用滑窗即可计算答案
又因为我们只考虑了2(𝑎𝑖 + 𝑎𝑗) ≤ bi + bj
的情况
再对每个三元组中的𝑎𝑖, bi
进行交换,计算一次答案即可。
时间复杂度O(n + nlog2 𝑛)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5+10;
const ll mod = 1e9+7;
struct node{ll a, b, c;}p[maxn];
bool cmp(node x, node y) {return (2*x.a-x.b) < (2*y.a-y.b);}
int n;
ll sum[maxn];
ll solve() {
sort(p+1, p+1+n, cmp); // 2a-b 从小到大排序
sum[0] = 0;
for(int i = 1; i <= n; i++)
sum[i] = (sum[i-1]+p[i].c)%mod;
int l = 1, r = n, sign = 0; ll k = 2*p[1].a-p[1].b; //二分找出最右边 on遍历也行
while(l <= r) {
int mid = (l+r)>>1;
ll t = 2*p[mid].a-p[mid].b;
if((k+t) <= 0) sign = mid, l = mid+1;
else r = mid-1;
}
ll res = 0; //双指针
for(l = 1, r = sign; l <= r; l++) {
while(r >= l && (2ll*p[l].a+2ll*p[r].a-p[l].b-p[r].b) > 0) r--;
if(r < l) break;
ll tmp = (sum[r]-sum[l-1]+mod)%mod;
res = (res + p[l].c*tmp%mod)%mod;
}
return res;
}
int main() {
cin>>n;
for(int i = 1; i <= n; i++) cin>>p[i].a>>p[i].b>>p[i].c;
ll ans = solve();
for(int i = 1; i <= n; i++) swap(p[i].a, p[i].b);
ans += solve();
ans%=mod;
cout<<ans<<endl;
}
G: 篮球校赛
选出每种能力的前 5 个人(很显然,如果一个人某个位置不在前 5,那么他不可能作为此位置出战),总共选出 25 人(可能重复)然后使用 DFS 判断答案即可(当然,这一步可以用状压 DP 优化时间,但没必要)
时间复杂度O(𝑛 + 5⁵)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
bool vis[maxn];
ll co[maxn][6];
ll mmax[6][6], ans = 0;
void dfs(int now, ll tmp){
if(now == 6){
ans = max(ans, tmp);
return;
}
for(int i = 1; i <= 5; i++){
if(vis[mmax[i][now]]) continue;
vis[mmax[i][now]] = 1;
dfs(now + 1, tmp + co[mmax[i][now]][now]);
vis[mmax[i][now]] = 0;
}
}
int main(){
ll n;
cin >> n;
for(int i = 1; i <= n; i++){
for(int j = 1; j <= 5; j++){
cin >> co[i][j];
for(int pos = 1; pos <= 5; pos++){
if(co[i][j] > co[mmax[pos][j]][j]){
for(int k = 5; k >= pos + 1; k--)
mmax[k][j] = mmax[k-1][j];
mmax[pos][j] = i;
break;
}
}
}
}
dfs(1, 0);
cout << ans << endl;
}
H: 分配学号
先排序,然后判断当前位置的同学的学号有几种选择的方案,累乘获得结果。
时间复杂度O(nlog₂ 𝑛)
#include <bits/stdc++.h>
typedef long long lld;
using namespace std;
const int MAXN = 1e5+5;
const int MOD = 1e9+7;
int n; lld a[MAXN];
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%lld", &a[i]);
sort(a, a+n);
lld ans = 1;
for (int i = 0, j; i < n; i = j)
for (j = i+1; j < n && a[j] < a[i]+j-i; j++)
ans = ans * (a[i]+j-i-a[j]+1) % MOD;
printf("%lld\n", ans);
return 0;
}
I: Gree 的心房
签到题,假设要走的路线是沿着地图的两条边走,那么最优的情况就是这 k 个物品都不挡路,所以判断 k 与(n-1)*(m-1)
的关系即可。
时间复杂度 O(1)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
ll n, m, k;
cin >> n >> m >> k;
if(k <= (n-1) * (m-1))
cout << n + m - 2;
else
cout << -1;
}
本文由 Time 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Jul 28, 2019 at 09:10 pm