A 牛牛与牛妹的RMQ
题目描述
某天，牛妹来找牛牛学习RMQ算法(Range Minimum/Maximum Query),即区间最值查询。也就是给定一个数组区间[L,R]，查询该子区间的最大值。
假设子数组的两端点下标分别为L,R的话RMQ(L,R)就表示数组区间[L,R]的最大值。
因为牛妹学会了RMQ算法，所以牛牛准备和她玩个游戏验证她真的学会了。
牛牛有一个长度大小为n的全排列数组，即数组中的数字是1~n，且每个数字仅出现1次。
她们一共玩了m轮游戏，在每轮游戏中，牛牛都准备了k个不同的下标。
然后牛牛和牛妹各自随机选出一个下标，并且两人所选下标可以是相同的。
假设牛牛选出的下标为a，牛妹选出的下标为b的话，那么本轮游戏的得分就是RMQ(min(a,b),max(a,b))。
请你告诉牛牛，对于每轮游戏可能的得分都有哪几种情况，以及这些情况出现的概率各是多大？
输入描述:
第一行输入一个正整数n,
接下来输入一行n个正整数 表示一个全排列数组，即数组中的数字是1~n，且每个数字仅出现1次。
接下来一行输入一个正整数表示玩游戏的轮数。
接下来m行，每行首先输入一个正整数表示该轮游戏可选的下标数目，然后紧跟着k个不同的正整数
表示每个下标。
输入数据保证
输出描述:
对于每个查询，首先按照可能出现的得分升序输出得分情况，然后输出该得分情况的概率。
概率用一个既约分数表述。
分析：
对于长度为 的区间，我们可以直接
遍历一遍统计答案.
对于长度大于 的区间，区间最大值的候选元素一定在长度为
的区间最大值集合中，因此只需要考虑长度为
的区间最大值的贡献.
先用单调栈记录每个数的极大值区间.
通过预处理出的极大值区间可以二分出当前这个数左边的可选下标个数 和 这个数右边的可选下标个数，即可计算贡献.
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)1e5;
const int N = (int)1e3;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
int n;
int a[M + 5];
int l[M + 5], r[M + 5];
int st[M + 5], tp;
int p[M + 5];
int lg[M + 5];
struct ST
{
int mx, id;
ST(int _mx = 0, int _id = 0): mx(_mx), id(_id){}
bool operator<(const ST& b)const
{
return mx < b.mx;
}
bool operator==(const ST& b)const
{
return id == b.id;
}
}f[M + 5][17];
vector<ST> v;
map<int, ll> mp;
ST ask(int l, int r)
{
int k = lg[r - l + 1];
return max(f[l][k], f[r - (1<<k) + 1][k]);
}
ll gcd(ll a, ll b)
{
return b ? gcd(b, a % b) : a;
}
void work()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
if(i > 1) lg[i] = lg[i / 2] + 1;
f[i][0] = ST(a[i], i);
}
for(int j = 1; j < 17; ++j)
{
for(int i = 1; i + (1<<j-1) <= n; ++i)
{
f[i][j] = max(f[i][j - 1], f[i + (1<<j-1)][j - 1]);
}
}
tp = 0;
for(int i = 1; i <= n; ++i)
{
while(tp && a[st[tp]] < a[i]) --tp;
if(tp) l[i] = st[tp] + 1;
else l[i] = 1;
st[++tp] = i;
}
tp = 0;
for(int i = n; i >= 1; --i)
{
while(tp && a[st[tp]] < a[i]) --tp;
if(tp) r[i] = st[tp] - 1;
else r[i] = n;
st[++tp] = i;
}
int m; scanf("%d", &m);
for(int i = 1, k; i <= m; ++i)
{
scanf("%d", &k);
for(int j = 1; j <= k; ++j) scanf("%d", &p[j]);
sort(p + 1, p + k + 1);
v.clear(); mp.clear();
for(int j = 1; j <= k; ++j) mp[a[p[j]]]++;
for(int j = 1; j < k; ++j) v.push_back(ask(p[j], p[j + 1]));
sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());
for(int j = v.size() - 1, L, R, c; j >= 0; --j)
{
L = (int)(upper_bound(p + 1, p + k + 1, v[j].id) - (p + 1))
- (int)(lower_bound(p + 1, p + k + 1, l[v[j].id]) - p)
+ 1;
R = (int)(upper_bound(p + 1, p + k + 1, r[v[j].id]) - (p + 1))
- (int)(lower_bound(p + 1, p + k + 1, v[j].id) - p)
+ 1;
c = p[lower_bound(p + 1, p + k + 1, v[j].id) - p] == v[j].id;
mp[v[j].mx] += 2 * (1ll * R * L - c);
}
ll d, k2 = 1ll * k * k;
for(auto x: mp)
{
d = gcd(x.second, k2);
printf("%d %lld/%lld\n", x.first, x.second / d, k2 / d);
}
}
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; scanf("%d", &T);
// while(T--) work();
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} B 牛牛抓牛妹
题目描述
牛牛和牛妹在下棋，棋盘的地图可以看成是一个n个点,m条边组成的图模型。牛妹控制一个棋子从1号点移动到n号点。
棋子可以在有边相邻的节点之间移动，且每次移动都只能走一步。
牛牛可以操作地图中k个关卡的通行状态，当关卡处于封锁状态时，棋子不能再移动到该节点。但是如果棋子已经位于关卡上面，不会立刻受到影响，但是在离开该节点后无法再返回处于封锁状态的节点。
牛妹的操作很简单，她每回合都会寻找当前位置到终点的最短路线移动，如果最短路线不唯一，她总是会选择移动到节点编号较小的节点。
牛牛可以在牛妹移动之前进行操作，改变关卡节点的状态（封锁关卡或者通行）。如果在牛牛操作之后，从牛妹到终点n不存在任何一条可行的通路，就认为牛牛困住了牛妹，此时就认为牛牛赢了牛妹。
现在请你帮助牛牛困住牛妹，牛牛会送你一个牛清楚作为帮助他的礼物。
输入的测试数据保证，游戏开始时牛牛至少存在一种可以成功困住牛妹取得胜利的方案。
输入描述:
第一行输入三个正整数n,m,k分别表示地图中节点的数目，边的数目，以及关卡数目。
接下来一行k个正整数表示关卡的位置。
接下来m行，每行两个正整数u,v表示一条边。
输出描述:
本题为伪交互，后台中的裁判程序将根据你的输出执行对应动作，当且仅当你在成功困住牛妹后打印"checkmate!"结束程序且此时使用的指令总条数不多于，裁判程序给出AC的结果。
你可以按照你的需要输出如下4种指令，要求你输出的指令总数不多于 。
1、lock X
执行该指令会封锁X节点，注意牛牛只能在关卡节点设卡封锁。如果你的程序试图封锁非关卡的节点，裁判程序会忽略此指令。
2、unlock X
执行该指令会解锁X节点，注意此指令的X也必须为关卡节点。
3、continue
执行该指令后表示牛牛的操作结束，牛妹向前移动一步，此时牛妹先寻找到达n的最短路径（存在多条最短路方案时会选择所有可行方案中字典序最小的方案，即下一步优先移动到节点编号较小的节点），然后进行移动。
由于牛牛的操作导致地图发生了变化，牛妹总是在移动前才开始考虑移动的方案。
如果已经将牛妹困住，不存在任何一条到n的路径时收到continue指令，牛妹会原地不动。
4、checkmate!
输出此指令后你需要结束你的程序，接下来裁判程序将会检查是否真的困住了牛妹，如果此时已经困住牛妹，则裁判程序将会给出AC的结果。
分析：
设 dis[j][i] 表示在关卡封锁状态为 j 的情况下，从 i 号点到 n 号点的最短距离.
同时维护出 nx[j][i] 表示在关卡封锁状态为 j 的情况下，牛妹当前处于 i 号点，下一步走向哪个点（被困住则为 -1）.
之后再 bfs 一遍记录关卡封锁状态为 0 从 1 号点出发到被困节点的路径.
路径上的状态转换映射成 “unlock” 和 “lock”，路径上的点的移动映射成 “continue”.
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)1e2;
const int N = (int)5e2;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
int n, m, k, p[8];
int cnt, head[M + 5];
struct enode
{
int v, nx;
}Edge[N * 2 + 5];
int id[M + 5];
bool vis[1<<7][M + 5];
int dis[1<<7][M + 5];
int nx[1<<7][M + 5];
void init()
{
cnt = 0;
for(int i = 1; i <= n; ++i)
{
head[i] = -1;
id[i] = -1;
for(int j = 0; j < (1<<k); ++j)
{
vis[j][i] = 0;
dis[j][i] = inf;
nx[j][i] = -1;
}
}
}
void add(int u, int v)
{
Edge[cnt].v = v;
Edge[cnt].nx = head[u];
head[u] = cnt++;
}
struct node
{
int u, dis;
node(int _u = 0, int _dis = 0): u(_u), dis(_dis){}
bool operator<(const node& b)const
{
return dis > b.dis;
}
};
priority_queue <node> q;
void dijkstra(int s)
{
for(int j = 0; j < (1<<k); ++j)
{
dis[j][s] = 0;
q.push(node(s, dis[j][s]));
while(!q.empty())
{
int u = q.top().u; q.pop();
if(vis[j][u] || ~id[u] && (j>>id[u]&1)) continue;
vis[j][u] = 1;
for(int i = head[u]; ~i; i = Edge[i].nx)
{
int v = Edge[i].v;
if(dis[j][v] > dis[j][u] + 1)
{
dis[j][v] = dis[j][u] + 1;
nx[j][v] = u;
q.push(node(v, dis[j][v]));
}
else if(dis[j][v] == dis[j][u] + 1)
{
nx[j][v] = min(nx[j][v], u);
}
}
}
}
}
struct node2
{
int u, state;
node2(int _state = 0, int _u = 0): state(_state), u(_u){}
} pre[1<<17][M + 5];;
queue<node2> q2;
void bfs(int state, int s)
{
for(int j = 0; j < (1<<k); ++j)
{
for(int i = 1; i <= n; ++i)
{
vis[j][i] = 0;
}
}
vis[state][s] = 1;
q2.push(node2(state, s));
while(!q2.empty())
{
int u = q2.front().u, state = q2.front().state; q2.pop();
int v = nx[state][u];
if(~v && !vis[state][v])
{
vis[state][v] = 1;
pre[state][v] = node2(state, u);
q2.push(node2(state, v));
}
for(int j = 0; j < (1<<k); ++j)
{
if(!vis[j][u])
{
vis[j][u] = 1;
pre[j][u] = node2(state, u);
q2.push(node2(j, u));
}
}
}
}
node2 getEnd()
{
for(int j = 0; j < (1<<k); ++j)
{
for(int i = 1; i < n; ++i)
{
if(nx[j][i] == -1 && vis[j][i]) return node2(j, i);
}
}
assert(0);
}
stack<node2> st;
void work()
{
scanf("%d %d %d", &n, &m, &k); init();
for(int i = 0; i < k; ++i) scanf("%d", &p[i]), id[p[i]] = i;
for(int i = 0, u, v; i < m; ++i)
{
scanf("%d %d", &u, &v);
add(u, v); add(v, u);
}
dijkstra(n);
bfs(0, 1);
node2 en = getEnd();
while(en.state != 0 || en.u != 1)
{
st.push(en);
en = pre[en.state][en.u];
}
int state = 0, u = 1;
while(!st.empty())
{
en = st.top(); st.pop();
if(state != en.state)
{
for(int j = 0; j < k; ++j)
{
if((state>>j&1) && !(en.state>>j&1)) printf("unlock %d\n", p[j]);
else if(!(state>>j&1) && (en.state>>j&1)) printf("lock %d\n", p[j]);
}
}
else if(u != en.u) printf("continue\n");
state = en.state, u = en.u;
}
printf("checkmate!\n");
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; scanf("%d", &T);
// while(T--) work();
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} C 牛牛与字符串border
题目描述
对于一个长度为n的字符串S,我们称字符串 为字符串的一个前缀，称字符串
为字符串的一个后缀。
牛牛最近学习了KMP算法，该算法可以在的复杂度内求出字符串所有前缀非自身的最长border。
用KMP的预处理函数处理长度大小为n的S串后，的值就是S串的非自身最长border。
同时，是S串第二长的border，
是S串第三长的border...以此类推,直到该变量的值为0。
字符串border是字符串匹配中的重要概念，它的定义如下：
若字符串S存在一个前缀 与后缀
完全匹配，则称S有一个长度大小为k的border。
现在给你一个长度大小为n的S串和一个正整数l，牛牛想要让S串满足同时具有长度大小为的border。
请你修改S串使得它满足条件，并且要求你修改的次数尽可能少。
如果满足修改次数最小的情况下有多种修改方案，你可以输出任意一种。
输入描述:
第一行输入一个正整数T，表示测试案例的组数，对于每组测试案例
首先输入两个正整数接下里输入一个长度大小为n的S串，S串仅包含小写英文字母。
输入数据保证
输出描述:
对于每个测试案例，输出修改后的字符串。要求修改的次数尽可能少，如果有多解，你可以输出任意一种。
分析：
显然字符串按照下标可以分成若干类.
找规律可以发现若 ，则类数为
; 否则为
.
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)1e5;
const int N = (int)2e4;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
int n, l;
char s[M + 5];
int cnt[26];
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
void work()
{
scanf("%d %d", &n, &l);
scanf("%s", s);
if(n == l) {printf("%s\n", s); return;}
int d;
if(n < 2 * l) d = n - l;
else d = gcd(n, l);
for(int i = 0; i < d; ++i)
{
memset(cnt, 0, sizeof(cnt));
for(int j = i; j < n; j += d) ++cnt[s[j] - 'a'];
int p = 0; for(int j = 0; j < 26; ++j) if(cnt[p] < cnt[j]) p = j;
for(int j = i; j < n; j += d) s[j] = p + 'a';
}
printf("%s\n", s);
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int T; scanf("%d", &T);
while(T--) work();
// work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} D 牛牛与整除分块
题目描述
整除分块，又称数论分块。是数论算法中的重要技巧，你可以在各种需要枚举因子的连续求和类问题中见到它的身影。如杜教筛，莫比乌斯反演化简后的整除分段求和等。
整除分块基于这样一个数学现象：对于任意正整数N，集合 的大小总是严格小于
。
例如当N=10时S={10,5,3,2,1}，这就使得对于类型的求和类问题，只要快速枚举S集合，就能在
级别的复杂度内解决问题。
符号是向下取整符，
表示不大于x的最大正整数
牛牛在学习整除分块这一算法后提出了一个新的问题，对于给定正整数N,x，令，时
在S中是第几大呢（去重降序排序后第几个）？
输入描述:
第一行输入一个正整数，表示测试案例的数目，对于每组案例。
一行两个正整数。
输出描述:
对于每个案例，输出一个正整数，即在集合S中降序排第几大。
分析：
当 时，
两两不同，因此
有
种取值.
当 时，
会取遍
，因此
有
种取值.
综上， 共有
种取值，接下来二分即可.
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)1e5;
const int N = (int)2e4;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
int read()
{
int x = 0, f = 1;
char ch = getchar();
while(!isdigit(ch))
{
if(ch == '-') f = -1;
ch = getchar();
}
while(isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
int n, x, q, s;
int cal(int k)
{
if(k <= q) return n / k;
else return n / (q + 1) - (k - q) + 1;
}
void print(int n)
{
if(n < 0)
{
putchar('-');
n = -n;
}
if(n > 9) print(n / 10);
putchar(n % 10 + '0');
}
void work()
{
n = read(), x = read();
q = (int)sqrt(n);
s = q + n / (q + 1);
int l = 1, r = s, mid;
while(l < r)
{
mid = (l + r + 1) / 2;
if(cal(mid) >= n / x) l = mid;
else r = mid - 1;
}
print(r);
putchar('\n');
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int T = read();
while(T--) work();
// work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} E 牛牛与跷跷板
题目描述
牛牛最近在玩“糖豆人”，其中有一关需要在跷跷板之间跳来跳去，达到终点。
游戏的界面可以抽象成一个2D的平面。
玩家一开始出生在第1块跷跷板上，然后需要到达终点所在的第n块跷跷板。
玩家可以在相邻的跷跷板之间跳跃，由于牛牛的操作不是很好，他总是会在跳跃时掉下悬崖。
所以牛牛拜托你来规划他的路线，使得他在跷跷板之间跳跃的次数尽可能少。
在这个问题中，所有的跷跷板都被抽象成是一个#1 \times n$ 的矩形，每个矩形较长的边都与坐标x轴平行。
玩家可以矩形中自由移动，并且如果两个矩形相邻，则可以“跳跃”一次移动到相邻的矩形上面。
我们认为两个矩形是相邻的，当且仅当他们接触边的接触长度不为0。即两矩形仅有一个角有公共点时不认为他们是相邻的。
输入数据保证，至少存在一种从1号板移动到n号板的移动方案。
所有跷跷板都是有实体的，所以保证它们不会“叠在一起”，即所有跷跷板两两的面积交为0。
输入描述:
第一行输入一个正整数表示跷跷板的数目，接下来n行，每行输入三个非负整数
表示每块跷跷板的y坐标，跷跷板的左边界，跷跷板的右边界。所有跷跷板都是有实体的，所以保证它们不会“叠在一起”，即所有跷跷板两两的面积交为0。
输出描述:
仅一行，一个非负整数，表示从第1块跷跷板移动到第n块跷跷板的最小跳跃次数。
分析：
尺取连边后 bfs 即可.
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)1e5;
const int N = (int)2e4;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
int n;
struct node
{
int l, r, id;
node(int _l, int _r, int _id): l(_l), r(_r), id(_id){}
};
vector<node> v[M + 5];
bool cmp(node a, node b)
{
return a.l < b.l;
}
int cnt, head[M + 5];
struct enode
{
int v, nx;
}Edge[M * 10 + 5];
int dis[M + 5];
void init()
{
cnt = 0;
for(int i = 1; i <= n; ++i)
{
head[i] = -1;
dis[i] = inf;
}
}
void add(int u, int v)
{
Edge[cnt].v = v;
Edge[cnt].nx = head[u];
head[u] = cnt++;
}
void bfs(int s)
{
dis[s] = 0;
queue<int> q;
q.push(s);
while(!q.empty())
{
int u = q.front(); q.pop();
for(int i = head[u]; ~i; i = Edge[i].nx)
{
int v = Edge[i].v;
if(dis[v] == inf)
{
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
}
void work()
{
scanf("%d", &n); init();
for(int i = 1, y, l, r; i <= n; ++i)
{
scanf("%d %d %d", &y, &l, &r);
v[y].push_back(node(l, r, i));
}
for(int i = 0, leni, leni_1, p1, p2; i <= M; ++i)
{
if(v[i].empty()) continue;
sort(v[i].begin(), v[i].end(), cmp);
leni = v[i].size(), leni_1 = (i ? v[i - 1].size() : 0), p1 = p2 = 0;
for(int j = 0; j < leni; ++j)
{
while(p1 < leni_1 && v[i - 1][p1].l < v[i][j].l) ++p1;
if(p1 < leni_1 && v[i - 1][p1].l < v[i][j].r)
{
while(p1 < leni_1 && v[i - 1][p1].l < v[i][j].r)
{
add(v[i - 1][p1].id, v[i][j].id);
add(v[i][j].id, v[i - 1][p1].id);
++p1;
}
--p1;
}
while(p2 < leni_1 && v[i - 1][p2].r <= v[i][j].l) ++p2;
if(p2 < leni_1 && v[i - 1][p2].l < v[i][j].r)
{
while(p2 < leni_1 && v[i - 1][p2].l < v[i][j].r)
{
add(v[i - 1][p2].id, v[i][j].id);
add(v[i][j].id, v[i - 1][p2].id);
++p2;
}
--p2;
}
if(j && v[i][j - 1].r == v[i][j].l)
{
add(v[i][j - 1].id, v[i][j].id);
add(v[i][j].id, v[i][j - 1].id);
}
}
}
bfs(1);
printf("%d\n", dis[n]);
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; scanf("%d", &T);
// while(T--) work();
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} F 牛牛与交换排序
题目描述
牛牛有一个数组，数组元素是1到n的排列，即数组的值在1~n范围内，且每个数字仅出现1次。
牛牛想要将该数组变为升序排列的，他可以进行如下的操作。
首先他要确定一个长度k，k的范围在1~n之间。
接下来他将会进行若干次操作。在每***作中他都可以选择一段长度为k的子数组，然后进行区间的翻转操作。
他可以做任意次数的操作，但是要求他每次选择的子数组区间满足，并且区间长度等于一开始选定的k，也就是说一旦某一次操作选择了数组的某个位置进行区间翻转操作，下一次做区间翻转的位置将会比上一次更靠右。
牛牛发现，并不总是存在一个k可以使得数组排序变为有序，请你告诉牛牛是否存在一个k能够在满足规则的情况下完成排序。
输入描述:
第一行输入一个正整数n表示数组的大小。
接下来输出一行n个正整数表示一个排列，即每个数的大小范围在1到n且每个正整数仅出现一次。
输出描述:
如果存在至少一个k能够使牛牛完成排序，请先在一行中输出一个"yes"，然后另起一行输出一个可以满足排序的k，要求k的范围在之间，如果有多解，你可以输出任意一个。
反之如果不存在任何一个k可以完成排序，请直接在一行输出一个"no"
分析：
只要一开始不是顺序那么 是确定的，之后边 check 边翻转即可.
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)1e5;
const int N = (int)2e4;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
int read()
{
int x = 0, f = 1;
char ch = getchar();
while(!isdigit(ch))
{
if(ch == '-') f = -1;
ch = getchar();
}
while(isdigit(ch))
{
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
int n;
int a[M + 5];
void work()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
int p = 1; while(p <= n && a[p] == p) ++p;
if(p == n + 1)
{
printf("yes\n1\n");
return;
}
int k = 1; while(a[p + k - 1] != p) ++k;
reverse(a + p, a + p + k);
for(int i = p + 1; i <= n; ++i)
{
if(a[i] == i) continue;
if(i + k - 1 > n || a[i + k - 1] != i)
{
printf("no\n");
return;
}
reverse(a + i, a + i + k);
}
printf("yes\n%d\n", k);
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T = read();
// while(T--) work();
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} G 牛牛与比赛颁奖
题目描述
牛牛举办了一场比赛，共有n支队伍来到现场参加比赛。该比赛共有m道题目，牛牛发现比赛的结果非常有意思，对于每一道题目。最终成功做出它的队伍都是连在一起的。即做出第i道题目的队伍是从到
连号的。
比赛结束后，牛牛准备为获奖队伍颁奖。由于比赛规则没有罚时这一项，为了保证相同AC数的队伍所获奖项相同，所以牛牛采取如下的方案颁奖。
首先是确定奖牌线，牛牛将所有参赛队伍按照最终通过题目总数降序排序。分别取排名为队伍的通过题目总数作为金、银、铜的奖牌线。
为向上取整符，
表示大于等于x的最小正整数。
特别的，要求奖牌线不得少于1题，当所划奖牌线为0题时，应视为1题。
当某支队伍通过题目的总数大于等于金、银、铜对应奖牌线的题目数时，就获得对应的奖牌。
同时满足多个奖牌线要求时，取满足奖项中的最高奖项，例如同时满足金、银、铜时应颁发金牌，同时满足银、铜时颁发银牌。
请你模拟比赛的颁奖过程，最后输出获得金、银、铜牌的队伍数目。
输入描述:
第一行输入两个正整数。
接下来输入m行，每行两个正整数 表示通过每道题的队伍是哪一段区间。
输出描述:
输出三个非负整数，表示最终获得金、银、铜牌的队伍数目。
分析：
大杂烩题...
差分 + 离散化，使劲模拟就过了.
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)1e5;
const int N = (int)2e4;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
int n, m;
int l[M + 5];
int r[M + 5];
int a[M * 4 + 5], len;
int b[M * 4 + 5];
int c[M + 5];
int tofind(int x)
{
return lower_bound(a + 1, a + len + 1, x) - a;
}
int cal(int rk)
{
for(int i = m; i >= 0; --i)
{
rk -= c[i];
if(rk <= 0) return i;
}
return 0;
}
void work()
{
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; ++i)
{
scanf("%d %d", &l[i], &r[i]);
a[++len] = l[i];
a[++len] = r[i];
a[++len] = r[i] + 1;
}
a[++len] = 1, a[++len] = n; a[++len] = n + 1;
// assert(len <= M * 4);
sort(a + 1, a + len + 1);
len = unique(a + 1, a + len + 1) - (a + 1);
for(int i = 1; i <= m; ++i)
{
// assert(tofind(l[i]) <= M);
// assert(tofind(r[i] + 1) <= M);
b[tofind(l[i])]++;
b[tofind(r[i] + 1)]--;
}
// assert(len <= M);
for(int i = 1; i <= len; ++i) b[i] += b[i - 1];
for(int i = 1; i < len; ++i)
{
// assert(0 <= b[i] && b[i] <= m);
c[b[i]] += a[i + 1] - a[i];
// printf("b[%d] = %d a[%d] - 1 = %d a[%d] = %d\n",
// i, b[i], i + 1, a[i + 1] - 1,
// i, a[i]);
}
int au = max(1, cal((n + 9) / 10));
int ag = max(1, cal((n + 3) / 4));
int cu = max(1, cal((n + 1) / 2));
int auc = 0, agc = 0, cuc = 0;
assert(m <= M);
for(int i = 1; i <= m; ++i)
{
if(i >= au) auc += c[i];
else if(i >= ag) agc += c[i];
else if(i >= cu) cuc += c[i];
}
printf("%d %d %d\n", auc, agc, cuc);
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; scanf("%d", &T);
// while(T--) work();
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} H 牛牛与棋盘
题目描述
牛牛发现国际象棋的棋盘图案特别好看，是黑白相间的。
众所周知，国际象棋的棋盘是88大小的，不过他现在想让你打印出一个nn(n为偶数)的国际象棋棋盘。
我们用字符'1'表示黑格，'0'表示白格。
棋盘左上角的格子为白格，规定与白格相邻的格子全部为黑格，与黑格相邻的格子全部为白格。
输入描述:
仅一行一个正整数保证n为偶数。
输出描述:
输出一个01矩阵，表示国际象棋的棋盘。
分析：
签到题.
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)1e5;
const int N = (int)2e4;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
void work()
{
int n; scanf("%d", &n);
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
printf("%d", (i + j) % 2);
}
printf("\n");
}
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; scanf("%d", &T);
// while(T--) work();
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} I 牛牛的“质因数”
题目描述
算数基本定理，又称唯一分解定理，算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积。即朴素的质因子分解算法就是利用了算数基本定理，依次枚举p判断N是否包含素因子p。
牛牛最近对于质因数分解产生了浓厚的兴趣。
牛牛定义了一个函数F(x)，它表示将x做质因数分解后得到的数字从小到大升序排列，然后将其“拼接”成一个大整数。
例如1500=,F(1500)=223555。
牛牛现在想要知道 的值。
由于这个结果非常大，所以你只用告诉牛牛最终答案对 取余数的结果即可。
输入描述:
仅一行一个正整数
输出描述:
仅一行，表示答案对 取余数的结果。
分析：
线性筛最小质因子给艹过去了（笑
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)4e6;
const int N = (int)2e4;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
bool is_prime[M + 5];
int prime[M + 5], cnt;
int v[M + 5];//最小质因子
int lg[M + 5];
ll p[M + 5];
void init()
{
for(int i = 1; i <= M; ++i) lg[i] = lg[i / 10] + 1;
p[0] = 1; for(int i = 1; i <= M; ++i) p[i] = p[i - 1] * 10 % mod;
memset(is_prime, 1, sizeof(is_prime));
is_prime[0] = is_prime[1] = 0;
for(int i = 2; i <= M; ++i)
{
if(is_prime[i])
{
prime[++cnt] = i;
v[i] = i;
}
for(int j = 1; j <= cnt && i * prime[j] <= M; ++j)
{
is_prime[i * prime[j]] = 0;
v[i * prime[j]] = prime[j];
if(i % prime[j] == 0)
{
break;
}
}
}
}
void work()
{
int n; scanf("%d", &n);
ll ans = 0, a, b;
for(int i = 2; i <= n; ++i)
{
a = 0, b = i;
while(b > 1)
{
a = (a * p[lg[v[b]]] % mod + v[b]) % mod;
b /= v[b];
}
ans = (ans + a) % mod;
}
printf("%lld\n", ans);
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; scanf("%d", &T);
// while(T--) work();
init();
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} J 牛牛想要成为hacker
题目描述
在算法竞赛中"hack"一般指用一组测试数据触发程序的缺陷，从而导致本来通过题目的AC代码无法通过该测试数据。
一般情况见得比较多的是用hack数据导致别人WA掉，当然也有一些会导致原本的AC代码TLE和MLE。
牛牛在一些简单的练习题时遇到了这样一个问题。
给定一个大小为n的数组a，然后请你判断数组元素是否能够从中选出三个组成一个三角形。
牛牛发现AC通过的代码中有这样一种暴力逻辑，该逻辑的伪代码如下。
FOR i = 1 ... n
FOR j = i + 1 ... n
FOR k = j + 1 ... n
IF isTriangle(a[i],a[j],a[k])
print("yes")
EXIT
END IF
END FOR
END FOR
END FOR
print("no")
EXIT 其实就是三重循环枚举数组的三个元素，检查是否为三角形。这段代码很取巧的地方在于它存在一种“短路”逻辑，一旦发现存在三角形就立刻终止程序。
这样在随机数据下其实很容易发现三角形，所以如果数据纯随机，显然这就是一段AC代码。
牛牛当然知道这个代码很明显就存在缺陷，如果数据构造的好的话应该可以卡TLE，但是牛牛发现，他并不会构造出能够hack这个暴力算法的数据，所以他请你来帮他。
我们以这段程序调用isTriangle的次数作为时间复杂度的计算依据，请你构造数据hack这段暴力程序，使它TLE掉。
输入描述:
第一行输入一个正整数n)表示需要你构造的数组大小。
输出描述:
输出n个正整数，正整数的范围在之间，要求该暴力程序在运行过程中调用isTriangle函数的次数不得少于
分析：
直接看代码就好惹.
代码实现：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
const int M = (int)1e5;
const int N = (int)2e4;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const ll mod = (ll)1e9 + 7;
ll f[M + 5];
void init()
{
f[0] = 1, f[1] = 2;
for(int i = 2; i <= 40; ++i)
{
f[i] = f[i - 1] + f[i - 2];
}
}
void work()
{
int n; scanf("%d", &n);
for(int i = 1; i <= min(40, n); ++i) printf("%lld ", f[i]);
for(int i = 41; i <= n; ++i) printf("1 ");
printf("\n");
}
int main()
{
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
// int T; scanf("%d", &T);
// while(T--) work();
init();
work();
// cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
return 0;
} 
京公网安备 11010502036488号