苏州网站建设网络,网站建设与开发教学大纲,企业解决方案公司排名,网站开发项目外包还好题很温柔#xff0c;温柔得我差点没做完 文章目录A#xff1a;Valeriy and Deque题意题解代码实现B#xff1a;Tolik and His Uncle题目题解代码实现C#xff1a;Serge and Dining Room题目题解代码实现A#xff1a;Valeriy and Deque
题意
给定一个双端队列#…还好题很温柔温柔得我差点没做完 文章目录AValeriy and Deque题意题解代码实现BTolik and His Uncle题目题解代码实现CSerge and Dining Room题目题解代码实现AValeriy and Deque
题意
给定一个双端队列然后给定一个operation每一个operation可以实现以下步骤 1.取出队列的前两个元素分别是AB。 2.如果AB那么A加入到这个队列的frontB加入到back否则A加入backB加入front。然后给你q个询问每一个询问是问你从原始数组开始执行第x次operation时A和B分别是多少 (2≤n≤10^5, 0≤q≤3⋅10^5) (0≤ai≤10^9)( 1≤mj≤10^18
输入输出样例 输入 5 3 1 2 3 4 5 1 2 10 输出 1 2 2 3 5 2 输入 2 0 0 0 输出
说明/提示 Consider all 10 steps for the first test in detail:2. [1, 2, 3, 4, 5] — on the first operation, A and B are 1 and 2 , respectively.So, 2 we write to the beginning of the deque, and 1 — to the end. We get the following status of the deque: [2, 3, 4, 5, 1] . 3. [2, 3, 4, 5, 1] ⇒A2,B3 . 4.[3,4,5,1,2] 5. [4, 5, 1, 2, 3] 6. [5, 1, 2, 3, 4] 7. [5, 2, 3, 4, 1] 8. [5,3,4,1,2] 9. [5, 4, 1, 2, 3] 10. [5, 1, 2, 3, 4] 11. [5, 2, 3, 4, 1]⇒A5,B2 .
题解
这个q这么大我们就不可能每一次都去重新模拟肯定超时 那我们就来思考AB之间的操作
显而易见当我们循环模拟到了a数组的最大值的时候 由于没有任何数大于它那么它就会开始霸占整个队列的front
而在这个时候就开始了一个n-1的循环节 每一次队列的第二个都会乖乖的跑到队列的最后等待被翻牌 这个时候我们就没有必要一次又一次的重复这个n-1的固定循环 可以用一个取模来进行操作 而从头开始模拟时未处理到Max的时候单独处理一下就可以了
最坏的情况就是Max在最后面n一个for便OK 我们的查询用O(1)完成 所以时间复杂度就是Oq
代码实现
#include cstdio
#include queue
using namespace std;
#define LL long long
#define MAXN 100005
struct node {int head, tail;
}change[MAXN];
int circle[MAXN];
deque int deq;
int n, q, Max, idx;
long long m;
int main() {scanf ( %d %d, n, q );for ( int i 1;i n;i ) {int x;scanf ( %d, x );deq.push_back ( x );if ( x Max ) {Max x;idx i;}}for ( int i 1;i idx;i ) {int A deq.front();deq.pop_front();int B deq.front();deq.pop_front();change[i].head A;change[i].tail B;if ( A B ) {deq.push_front( A );deq.push_back ( B );}else {deq.push_front( B );deq.push_back ( A );}}for ( int i 0;i n - 1;i ) {circle[i] deq.back ();int A deq.front();deq.pop_front();int B deq.front();deq.pop_front();deq.push_front( A );deq.push_back ( B );}for ( int i 1;i q;i ) {scanf ( %lld, m );if ( m idx )printf ( %d %d\n, change[m].head, change[m].tail );elseprintf ( %d %d\n, Max, circle[( m - idx ) % ( n - 1 )] );}return 0;
}BTolik and His Uncle
题目
你有一个n行m列的棋盘其中第i行第j列的格子标号为(i,j)。你需要从(1,1)开始遍历这个棋盘。每一次如果你在(x,y)你可以选择一个向量(dx,dy)并且移动到(xdx,ydy)这个格子上。 你不能离开这个棋盘同时每一个向量只能使用一次。你的任务是合理安排自己的行走路线使得每一个格子都只被经过一次。输出这个方案。 n, m ( 1≤n⋅m≤10^6)
输入输出样例 输入 2 3 输出 1 1 1 3 1 2 2 2 2 3 2 1 输入 1 1 输出 1 1 说明/提示
The vectors from the first example in the order of making jumps are (0, 2), (0, -1), (1, 0), (0, 1), (0, -2) .
题解
向量不一样的意思是dxdy不能同时一样 如我用过11就不能再用但是可以用12或者31
我们先来思考只有一行的情况 那么肯定可以(1,1)(1,m)(1,2)(1,m-1)…每一次dy都在减小而且还分了正负 我们再来思考只有一列的情况类比行 肯定也可以(1,1)(n,1)(2,1)(n-1,1)…每一次dx都在减小而且也分了正负
那么二维又有行又有列怎么办呢 我们就行列一起跳呗先循环行列跳完后行再往中间移动 (1,1)(n,m)(1,2)(n,m-1)…(1,m)(n,1)(2,1)(n-1,m)…
最后特别判断n为奇数m为奇数的情况即可
代码实现
这道题就是找到了方法直接暴力就可以了 代码可以长得五花八门 我就对自己的代码很不满意有点丑 但是是自己打的能怎么办呢跪着也要宠下去麻痹自己其实写得还不错
#include cstdio
int n, m, cnt;
void dfs ( int x, int y ) {cnt ;if ( y m ) return;printf ( %d %d\n, x, y );if ( cnt % 2 )dfs ( n - x 1, m - y 1 );elsedfs ( n - x 1, m - y 2 );
}
int main() {scanf ( %d %d, n, m );for ( int i 1;i ( n 1 );i ) {cnt 0;dfs ( i, 1 );}if ( n % 2 ) {for ( int i 1;i ( m 1 );i )printf ( %d %d\n%d %d\n, ( n 1 ) 1, i, ( n 1 ) 1, m - i 1 );if ( m % 2 ) printf ( %d %d\n, ( n 1 ) 1, ( m 1 ) 1 );}return 0;
}CSerge and Dining Room
题目
给你n个物品每个物品一个的价格和m个现在依次排在队里的人手上的钱每个人都会尽可能把钱用完去买一样东西即买当前物品中能买的价值最高的不能买就不买走人问m个人排完之后剩下的价值最高的物品价格是多少。 有q次操作输入操作方案 1.如果是1输入i,x把ai变成xi≤n 2.如果是2输入ix把bi变成x 1≤i≤m ( 1≤n,m≤300000 )1≤ai, bi≤10^6) (1≤q≤300000 ) ( 1≤x≤10^6)
题解
如果在更改某个值后发现aiaj但是ai选的菜biaj选的菜bj那么肯定要交换 换过去换过来你会发现下标早已经打乱所以我们就不需要考虑用下标来做 用什么呢
题意一句话找到一个最大的x 使得满足钱大于等于x的人的数量money要小于价格大于等于x的数量pirce 好好理解
我们可以让所有ai≥物品价格x的1而所有bi≥人手里钱数量y的-1 因为我们把ai和bi用相同的东西一起处理的所以区分一下/-1
为什么这么做呢想想 当我们加入ai的时候所有小于等于ai的aj的money都应该1 当我们加入bi的时候所有小于等于bi的bj的price都应该1 而上面说过ai和bi使用同一个东西操作那么bi1就意味着ai-1 所以我们才物品价格1钱数-1
而我们再操作ai的时候不知道整个数组有多少aj是≤ai的也不知道bi的情况 而我们的操作却要把所有满足的都进行/-1操作那么怎么做呢
这时就想到了线段直接来进行对于值维护修改直接把1~x的所有值/-1 如果i点1就意味着后面有一道菜的价格大于等于ai -1则意味着后面有一个人的钱数大于等于ai 所以才有代码下面从1~ai修改 还不用超时多好再用lazy打标优化一波
代码实现
#include cstdio
#include iostream
using namespace std;
#define MAXN 300005
#define MAX 1000000
int n, m, q;
int opt, idx, ip;
int a[MAXN], b[MAXN];
int tree[MAX 2];
int lazy[MAX 2];
int maxval[MAX 2];void push_down ( int num ) {if ( lazy[num] ) {lazy[num 1] lazy[num];lazy[num 1 | 1] lazy[num];maxval[num 1] lazy[num];maxval[num 1 | 1] lazy[num];lazy[num] 0;}
}void update ( int l, int r, int L, int R, int num, int val ) {if ( L l r R ) {lazy[num] val;maxval[num] val;return;}push_down ( num );int mid ( l r ) 1;if ( L mid ) update ( l, mid, L, R, num 1, val );if ( mid R ) update ( mid 1, r, L, R, num 1 | 1, val );maxval[num] max ( maxval[num 1], maxval[num 1 | 1] );
}int query ( int l, int r, int num ) {if ( l r ) return l;push_down ( num );int mid ( l r ) 1;if ( maxval[num 1 | 1] 0 ) return query ( mid 1, r, num 1 | 1 );return query ( l, mid, num 1 );
}int main() {scanf ( %d %d, n, m );for ( int i 1;i n;i ) {scanf ( %d, a[i] );update ( 1, MAX, 1, a[i], 1, 1 );}for ( int i 1;i m;i ) {scanf ( %d, b[i] );update ( 1, MAX, 1, b[i], 1, -1 );}scanf ( %d, q );for ( int i 1;i q;i ) {scanf ( %d %d %d, opt, idx, ip );if ( opt 1 ) {update ( 1, MAX, 1, a[idx], 1, -1 );update ( 1, MAX, 1, ip, 1, 1 );a[idx] ip;}else {update ( 1, MAX, 1, b[idx], 1, 1 );update ( 1, MAX, 1, ip, 1, -1 );b[idx] ip;}if ( maxval[1] 0 ) printf ( %d\n, query ( 1, MAX, 1 ) );else printf ( -1\n );}return 0;
} 好了今天的题比较容易理解仙女最近被几道ex至极的题给卡住了 博客有点男鞋不要急慢慢来有任何问题都可以留言 不要太想小哥哥我~~
