自适应网站开发书籍,租用服务器网站,网站总是跳转dede58,如何外贸网络推广文章目录T1#xff1a;糖果机器solutioncodeT2#xff1a;手套solutioncodeT3#xff1a;甲虫solutioncodeT4#xff1a;选举solutioncodeT1#xff1a;糖果机器
solution
考虑从第iii个糖果出发能到达第jjj个#xff0c;则有Tj−Ti≥∣Sj−Si∣T_j-T_i≥|S_j-S_i|Tj…
文章目录T1糖果机器solutioncodeT2手套solutioncodeT3甲虫solutioncodeT4选举solutioncodeT1糖果机器
solution
考虑从第iii个糖果出发能到达第jjj个则有Tj−Ti≥∣Sj−Si∣T_j-T_i≥|S_j-S_i|Tj−Ti≥∣Sj−Si∣ {Tj−Ti≥Sj−SiTj−Ti≥Si−Sj{TiSi≥TjSjTi−Si≥Tj−Sj\left\{ \begin{aligned} T_j-T_i≥S_j-S_i \\ T_j-T_i≥S_i-S_j\\ \end{aligned} \right.\left\{ \begin{aligned} T_iS_i\ge T_jS_j\\ T_i-S_i\ge T_j-S_j\\ \end{aligned} \right.{Tj−Ti≥Sj−SiTj−Ti≥Si−Sj{TiSi≥TjSjTi−Si≥Tj−Sj 发现这其实是函数同构体
令ATiSi,BTi−SiAT_iS_i,BT_i-S_iATiSi,BTi−Si则可转化为 {Ai≥AjBi≥Bj\left\{ \begin{aligned} A_i\ge A_j\\ B_i\ge B_j\\ \end{aligned} \right.{Ai≥AjBi≥Bj 又发现此题就是一个二维偏序问题 其实就是noip普及组1999导弹拦截
二维偏序问题一般是一维时间轴有序然后二维套树状数组总体上复杂度是logloglog级别
code
#include set
#include cstdio
#include algorithm
using namespace std;
#define maxn 100005
struct node {int s, t, id;friend bool operator ( const node x, const node y ) {return x.s x.t y.s y.t;}
}p[maxn];
set node st;
int n, tot;bool cmp( node x, node y ) {return ( x.t - x.s y.t - y.s ) ? ( x.t x.s y.t y.s ) : ( x.t - x.s y.t - y.s );
}int main() {scanf( %d, n );for( int i 1;i n;i )scanf( %d %d, p[i].s, p[i].t );sort( p 1, p n 1, cmp );for( int i 1;i n;i ) {set node :: iterator it st.upper_bound( p[i] );if( it st.begin() ) p[i].id tot;else it --, p[i].id it-id, st.erase( it );st.insert( p[i] );}printf( %d\n, tot );for( int i 1;i n;i )printf( %d %d %d\n, p[i].s, p[i].t, p[i].id );return 0;
}T2手套
solution code
#include cstdio
#include algorithm
using namespace std;
#define maxn 20
struct node {int x, y;
}p[1 maxn];
int n;
int a[maxn], b[maxn];bool cmp( node s, node t ) {return ( s.x t.x ) ? ( s.y t.y ) : ( s.x t.x );
}void update( long long ansx, long long ansy, long long x, long long y ) {if( ( x y ansx ansy ) || ( x y ansx ansy x ansx ) )ansx x, ansy y;
}int main() {scanf( %d, n );for( int i 0;i n;i )scanf( %d, a[i] );for( int i 0;i n;i )scanf( %d, b[i] );int m 1 n;for( int i 0;i m;i )for( int j 0;j n;j )if( i j 1 ) p[i].x a[j];for( int i 0;i m;i )for( int j 0;j n;j )if( i j 1 ) p[m - 1 - i].y b[j];long long flagx p[m - 1].x, flagy p[0].y, ansx flagx, ansy flagy;sort( p, p m, cmp );for( int i m - 1, y 0;~ i;i -- ) {if( p[i].x ! flagx y ! flagy )update( ansx, ansy, p[i].x 1, y 1 );y max( p[i].y, y );}printf( %lld\n%lld\n, ansx, ansy );return 0;
}T3甲虫
solution
区间dp还是一眼就看得出来只不过不知道怎么处理时间问题考场上错误代码都能骗40 正着不行就反着考虑
code
#include cstdio
#include cstring
#include iostream
#include algorithm
using namespace std;
#define maxn 305
#define ll long long
#define inf 0x3f3f3f3f
int n, m, k;
int x[maxn];
ll dp[2][maxn][maxn];
int vis[2][maxn][maxn];long long dfs( int t, int l, int r ) {if( r - l k ) return 0;if( vis[t][l][r] k ) return dp[t][l][r];vis[t][l][r] k;int p ( t ? r : l );ll ans dp[t][l][r];ans inf;if( l ! 1 ) ans min( ans, dfs( 0, l - 1, r ) ( x[p] - x[l - 1] ) * ( k - ( r - l ) ) );if( r ! n ) ans min( ans, dfs( 1, l, r 1 ) ( x[r 1] - x[p] ) * ( k - ( r - l ) ) );return ans;
}int main() {scanf( %d %d, n, m );for( int i 1;i n;i )scanf( %d, x[i] );x[ n] 0;sort( x 1, x n 1 );int pos;for( int i 1;i n;i )if( ! x[i] ) { pos i; break; }ll ans 0;for( k 0;k n;k )ans max( ans, 1ll * m * k - dfs( 0, pos, pos ) );printf( %lld, ans );return 0;
}T4选举
solution code
#include cstdio
#include iostream
using namespace std;
#define maxn 500005
struct node {int minn, maxx, ans;node() {}node( int Min, int Max, int Ans ) {minn Min, maxx Max, ans Ans;}friend node operator ( const node x, const node y ) {return node( min( x.minn, y.minn ), max( x.maxx, y.maxx ), max( y.maxx - x.minn, max( x.ans, y.ans ) ) );}
}t[maxn 2];
int n, Q;
char s[maxn];
int pre[maxn];void build( int num, int l, int r ) {if( l r ) {t[num] node( pre[l], pre[l], 0 );return;}int mid ( l r ) 1;build( num 1, l, mid ), build( num 1 | 1, mid 1, r );t[num] t[num 1] t[num 1 | 1];
}node query( int num, int l, int r, int L, int R ) {if( L l r R ) return t[num];int mid ( l r ) 1;if( R mid ) return query( num 1, l, mid, L, R );else if( mid L ) return query( num 1 | 1, mid 1, r, L, R );else return query( num 1, l, mid, L, R ) query( num 1 | 1, mid 1, r, L, R );
}int main() {scanf( %d %s %d, n, s 1, Q );for( int i 1;i n;i )pre[i] pre[i - 1] ( s[i] T ? -1 : 1 );build( 1, 0, n ); while( Q -- ) {int l, r;scanf( %d %d, l, r );node ans query( 1, 0, n, l - 1, r );printf( %d\n, ans.ans - ( pre[r] - pre[l - 1] ) );}return 0;
}
