网上书店网站模板,菏泽公司网站建设,那种网站建设软件最好,网站推广方法有几个文章目录 [COCI2010-2011#7] GITARA题目背景题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 提示样例 1 解释样例 2 解释数据规模及约定说明 思路解析非常无脑非常长的CODE巨佬的简短CODE [COCI2010-2011#7] GITARA
题目链接#xff… 文章目录 [COCI2010-2011#7] GITARA题目背景题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1 样例 #2样例输入 #2样例输出 #2 提示样例 1 解释样例 2 解释数据规模及约定说明 思路解析非常无脑非常长的CODE巨佬的简短CODE [COCI2010-2011#7] GITARA
题目链接https://www.luogu.com.cn/problem/P6704
题目背景
Darko 有一个想象的外星朋友他有十亿根手指。外星人快速拿起吉他在网上找到一段简单的旋律并开始弹奏。
这个吉他像寻常一样有六根弦令其用 1 1 1 到 6 6 6 表示。每根弦被分成 P P P 段令其用 1 1 1 到 P P P 表示。
旋律是一串的音调每一个音调都是由按下特定的一根弦上的一段而产生的如按第 4 4 4 弦第 8 8 8 段。如果在一根弦上同时按在几段上产生的音调是段数最大的那一段所能产生的音调。
例对于第 3 3 3 根弦第 5 5 5 段已经被按若你要弹出第 7 7 7 段对应音调只需把按住第 7 7 7 段而不需放开第 5 5 5 段因为只有最后的一段才会影响该弦产生的音调(在这个例子中是第 7 7 7 段)。类似如果现在你要弹出第 2 2 2 段对应音调你必须把第 5 5 5 段和第 7 7 7 段都释放。
请你编写一个程序计算外星人在弹出给定的旋律情况下手指运动的最小次数。
题目描述
你有一个 6 × P 6 \times P 6×P 的矩阵 A A A初始状态皆为 0 0 0。
对于所有要求 ( i , j ) (i,j) (i,j)
你需要满足要求 此时 A i , j A_{i,j} Ai,j 状态为 1 1 1。 对于 A i , j k ( k 0 ) A_{i,jk} (k0) Ai,jk(k0) 状态为 0 0 0。
你在满足要求的情况下需要求状态转换最小次数。
输入格式
第一行包含两个正整数 n n n P P P。它们分别指旋律中音调的数量及每根弦的段数。
下面的 n n n 行每行两个正整数 i i i j j j分别表示能弹出对应音调的位置——弦号和段号其为外星人弹奏的顺序。
输出格式
一个非负整数表示外星人手指运动次数最小值。
样例 #1
样例输入 #1
5 15
2 8
2 10
2 12
2 10
2 5样例输出 #1
7样例 #2
样例输入 #2
7 15
1 5
2 3
2 5
2 7
2 4
1 5
1 3样例输出 #2
9提示
样例 1 解释
所有的音调都是由第二根弦产生的。首先按顺序按 8 8 8 10 10 10 12 12 12 c o u n t 3 count3 count3。然后释放第 12 12 12 段 c o u n t 4 count4 count4。最后按下第 5 5 5 段释放第 8 8 8 10 10 10 段 c o u n t 7 count7 count7。
样例 2 解释
对于每个操作分别需要 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 0 0 0 2 2 2 次手指运动。
数据规模及约定
按下或释放一段弦各计一次手指运动。弹弦不算手指的移动而是一个弹吉他的动作。指你不需要管他怎么弹的只需要按就是啦说不定他可以用超能力呀
对于 100 % 100\% 100% 的数据 n ≤ 5 × 1 0 5 n \le 5 \times 10^5 n≤5×105 2 ≤ P ≤ 3 × 1 0 5 2 \le P \le 3 \times 10^5 2≤P≤3×105
说明
本题满分 70 70 70 分。
译自 COCI2010-2011 CONTEST #7 T3 GITARA 思路解析
有六根弦每根弦只有最前面的一段发生所以我们可以用六个栈来模拟六根弦。
如果要按的段比当前最大的段要大就直接压栈如果要按的段比当前最大的段要小那么不断弹栈直到栈空或者没有比它小的段停止判断当前段是否跟需要按得段一致一致就不需要操作比它小就需要压栈
非常无脑非常长的CODE
#include iostream
#include cstring
#include algorithm
#define ll long longusing namespace std;const int N 3000005, p 300005;
int stk[8][N];
int n, P;
int t1 -1;
int t2 -1;
int t3 -1;
int t4 -1;
int t5 -1;
int t6 -1;int main(){cin n P;int ans 0;int i, j;while(n--){scanf(%d%d, i, j);if(i 1){while(t1 -1 stk[1][t1] j){t1--;ans;}if(t1 -1 || stk[1][t1] j){stk[1][t1] j;ans;}}else if(i 2){while(t2 -1 stk[2][t2] j){t2--;ans;}if(t2 -1 || stk[2][t2] j){stk[2][t2] j;ans;}}else if(i 3){while(t3 -1 stk[3][t3] j){t3--;ans;}if(t3 -1 || stk[3][t3] j){stk[3][t3] j;ans;}}else if(i 4){while(t4 -1 stk[4][t4] j){t4--;ans;}if(t4 -1 || stk[4][t4] j){stk[4][t4] j;ans;}}else if(i 5){while(t5 -1 stk[5][t5] j){t5--;ans;}if(t5 -1 || stk[5][t5] j){stk[5][t5] j;ans;}}else if(i 6){while(t6 -1 stk[6][t6] j){t6--;ans;}if(t6 -1 || stk[6][t6] j){stk[6][t6] j;ans;}}}cout ans endl;
} 代码虽然 A C AC AC但是显得特别sb复用很多不优雅不美观但是想不到怎么优化于是看了题解果然还是题解大神nb啊用数组存了栈顶指针大大节省了代码量tql%%%%%%%%果然还是我太菜了 _
巨佬的简短CODE
#includeiostream
#includecstdio
using namespace std;
int n,p,x,y,s,sum[7],a[7][300005];
int main()
{scanf(%d%d,n,p);for(int i1;in;i){scanf(%d%d,x,y);while(sum[x]1a[x][sum[x]]y)//判断栈是否空还有比较栈顶{sum[x]--;//减减s;//累加次数 }if(a[x][sum[x]]y)continue;//如果与栈顶相同就跳过a[x][sum[x]]y;//入栈s;//累加次数} printf(%d,s);//输出次数return 0;
}
来源https://blog.csdn.net/weixin_45524309/article/details/108541871
