全美网站开发,类似wordpress 简单,建个网站在哪备案,网站开发jquery文章目录考试复盘A#xff1a;灯(light)B#xff1a;十字路口(crossing)C#xff1a;密室逃脱(escape)考试复盘
第一题分块虽然明显#xff0c;但是说实话自己没怎么做过分块的题 就不会做大块的处理。。。(;_) 今天听H老说分块可以成替代数据结构的骗分暴力对拍神器 这么…
文章目录考试复盘A灯(light)B十字路口(crossing)C密室逃脱(escape)考试复盘
第一题分块虽然明显但是说实话自己没怎么做过分块的题 就不会做大块的处理。。。(;¬_¬) 今天听H老说分块可以成替代数据结构的骗分暴力对拍神器 这么一听似乎非常有用今晚要刷一刷了 但是我的暴力竟然又挂了(*Д)つ匚___
第二题没有反应过来这个周期其实相当于是找环暴力判的额结果不言而喻
第三题虽然也看得出来是DPDPDP但是那个转移方程式确实不可能是我的实力想得到的嘤嘤嘤~~ 一般这种有时间关卡的们隧道等等这种在一条“路”上的1−n1-n1−n问题一般都是考察的DPDPDP贪心转化为最短路等图论问题最多来个线段树分治
今天的题目总的来说考什么算法是非常显而易见的但是细节以及实现却成为了难点 大纲清晰考察刁钻千言万语只能化作一句好很好非常好 A灯(light)
分块 连续段数等于开着的灯数减相邻两个都开着的灯对数 次数n\sqrt{n}n的颜色直接暴力枚举所在位置更新 次数n\sqrt{n}n的颜色维护与这种颜色相邻的开着的灯数 每次我们改变n\sqrt{n}n的颜色时直接用这个算答案
#include map
#include cmath
#include cstdio
#include vector
#include algorithm
using namespace std;
#define Pair pair int, int
#define maxn 100005
#define Block 350
vector int pos[maxn];
int n, m, Q, ans;
int c[maxn], cnt[maxn], t[maxn], big[Block], MS[maxn];
int g[Block][Block];
bool vis[maxn];int main() {freopen( light.in, r, stdin );freopen( light.out, w, stdout );scanf( %d %d %d, n, m, Q );for( int i 1;i n;i ) {scanf( %d, c[i] );if( c[i] c[i - 1] ) i --, n --;else;}for( int i 0;i n;i ) {pos[c[i]].push_back( i ); cnt[c[i]] ;}int block sqrt( n ), ip 0;for( int i 1;i m;i )if( cnt[i] block ) big[ ip] i, MS[i] ip;else;for( int i 1;i n;i )g[MS[c[i]]][MS[c[i 1]]] , g[MS[c[i 1]]][MS[c[i]]] ;while( Q -- ) {int x;scanf( %d, x );if( vis[x] ) {ans - cnt[x];if( MS[x] ) {ans t[x];for( int i 1;i ip;i )if( vis[big[i]] ) ans g[i][MS[x]];else;}else {for( int i 0;i pos[x].size();i ) {ans vis[c[pos[x][i] - 1]];ans vis[c[pos[x][i] 1]];t[c[pos[x][i] - 1]] --;t[c[pos[x][i] 1]] --;}}}else {ans cnt[x];if( MS[x] ) {ans - t[x];for( int i 1;i ip;i )if( vis[big[i]] ) ans - g[i][MS[x]];else;}else {for( int i 0;i pos[x].size();i ) {ans - vis[c[pos[x][i] - 1]];ans - vis[c[pos[x][i] 1]];t[c[pos[x][i] - 1]] ;t[c[pos[x][i] 1]] ;}}}vis[x] ^ 1;printf( %d\n, ans );}return 0;
}B十字路口(crossing) 设xix_ixi表示第iii次观察的时间(对周期取模) 如果有一个灯在两次观察中都是红灯可以得到一个形如xi−xjkx_i-x_jkxi−xjk的方程 将这看做是iii指向jjj权值为kkk的有向边那么一个环的长度显然是周期的倍数 不难证明最小环就是周期用floydfloydfloyd求出时间复杂度为O(m3nm2)O(m^3nm^2)O(m3nm2) 同理设yiy_iyi表示第iii个灯由红变绿的时间一样的方法时间复杂度为O(n3mn2)O(n^3mn^2)O(n3mn2) 结合两种方法可以做到O(nmnm)O(nm\sqrt{nm})O(nmnm)哪个小用哪种
#include cstdio
#include vector
#include cstring
using namespace std;
#define maxn 400
#define maxm 100005
#define inf 0x3f3f3f3f
vector int G[maxm];
int n, m;
int dis[maxn][maxn];int main() {freopen( crossing.in, r, stdin );freopen( crossing.out, w, stdout );scanf( %d %d, n, m );for( int i 1;i m;i )G[i].resize( n );for( int i 1;i m;i )for( int j 0;j n;j )scanf( %d, G[i][j] );memset( dis, 0x3f, sizeof( dis ) );int ans inf;if( m n ) {for( int i 1;i m;i )for( int k i 1;k m;k )for( int j 0;j n;j )if( G[i][j] G[k][j] ) {if( G[i][j] G[k][j] )dis[i][k] G[i][j] - G[k][j];elsedis[k][i] G[k][j] - G[i][j];}else;for( int k 1;k m;k )for( int i 1;i m;i )for( int j 1;j m;j )dis[i][j] min( dis[i][j], dis[i][k] dis[k][j] );for( int i 1;i m;i )ans min( ans, dis[i][i] );}else {for( int j 0;j n;j )for( int k j 1;k n;k )for( int i 1;i m;i )if( G[i][j] G[i][k] ) {if( G[i][j] G[i][k] )dis[j][k] G[i][j] - G[i][k];elsedis[k][j] G[i][k] - G[i][j];}else;for( int k 0;k n;k )for( int i 0;i n;i )for( int j 0;j n;j )dis[i][j] min( dis[i][j], dis[i][k] dis[k][j] );for( int i 0;i n;i )ans min( ans, dis[i][i] );}if( ans inf ) printf( -1\n );else printf( %d\n, ans );return 0;
}C密室逃脱(escape) #include cstdio
#include iostream
using namespace std;
#define Edge 20000
#define maxn 1005
int n, m;
int a[maxn], b[maxn];
int dp[maxn][Edge 5];int main() {freopen( escape.in, r, stdin );freopen( escape.out, w, stdout );scanf( %d %d, n, m );for( int i 1;i n;i )scanf( %d %d, a[i], b[i] );for( int i 0;i m;i ) dp[1][i] i;for( int i 1;i n;i ) {int maxx 0;for( int j 0;j a[i];j ) {dp[i 1][j b[i]] max( dp[i 1][j b[i]], dp[i][j] b[i] );maxx max( maxx, dp[i][j] );}for( int j 0;j b[i];j )dp[i 1][j] max( dp[i 1][j], maxx j );for( int j a[i];j a[i] b[i];j )dp[i 1][j - a[i]] max( dp[i 1][j - a[i]], dp[i][j] );for( int j a[i] b[i];j Edge;j )dp[i 1][j] max( dp[i 1][j], dp[i][j] );}int ans 0;for( int i 0;i Edge;i )ans max( ans, dp[n][i] );printf( %d\n, ans );return 0;
}
