啥也不说了，菜就得挨打。
题目大意：给定一个数组a[i]，长度为n<=1e5，你必须在其中删除一个数，使得最长连续上升子序列最长。问你最长多长。
思路：dp[i][0]表示i-1之前都没有删除的以i为结尾的最长上升子串的长度，dp[i][1]表示i-1之前已经删除过的以i为结尾的最长上升子串的长度。（比赛种我用的是dp[i][1]表示在i点删除，dp[i][2]表示在i之前删除，这样也可以，但是转移比较麻烦，还是上面这种写法最方便）。
然后递推的时候注意，如果删除了i-1，你必须与i-2这个状态进行比较，就是考虑a[i]和a[i-2]的大小关系，具体看代码
#include <stdio.h>#include <iostream>#include <vector>#include <algorithm>using namespace std;const int maxn=1e5+10;int a[maxn];int dp[maxn][2];const int INF=0x3f3f3f3f;signed main(){int n;freopen("E:\mingw\in.txt","r",stdin); freopen("E:\mingw\out2.txt","w",stdout);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}dp[1][1]=0;dp[1][0]=1;for(int i=2;i<=n;i++){if(a[i]>a[i-1]){dp[i][1]=max(dp[i-1][1]+1,dp[i-1][0]);dp[i][0]=dp[i-1][0]+1;}else{dp[i][0]=1;if(a[i]>a[i-2]){dp[i][1]=max(1,dp[i-2][0]+1);}else{dp[i][1]=1;}}}int ans=0;for(int i=1;i<=n;i++){ans=max(ans,dp[i][1]);}printf("%dn",ans);return 0;} 题目大意：给定n个任务，每个任务有k个子任务，每个大大任务的k个子任务耗时都是一定的，每完成一个子任务，得到p的分，如果完成了一个大任务的所有小任务，得到p*k+q的分，现在你有m的时间，问你最多能得到多少分？
m<=2e9，每个子任务t<=1e6，n,k<=100
思路：直接枚举完成多少个大任务，在完成多少个大任务后，对小任务排序，因为我不会再完成新的大任务了，所以我肯定是先将剩下的大任务中耗时最小的小任务都完成，然后去完成第二小的，然后第三小.......这样小任务就可以贪心解决了
#include <iostream>#include <algorithm>#include <stdio.h>#include <string.h>#define int long long using namespace std;const int maxn=100+10;int cost[maxn];signed main(){int n,k,m;scanf("%lld%lld%lld",&n,&k,&m);int sum=0;for(int i=1;i<=k;i++){scanf("%lld",&cost[i]);sum+=cost[i];}sort(cost+1,cost+n+1);int p,q;scanf("%lld%lld",&p,&q);int cnt=min(n,m/sum);if(cnt>=n){printf("%lldn",n*(p*k+q));return 0;}int ans=0;for(int i=0;i<=cnt;i++){int temp=m-i*sum;int cur=i*(p*k+q);for(int j=1;j<=k;j++){for(int t=i+1;t<=n;t++){if(temp>=cost[j]){temp-=cost[j];cur+=p;}else{temp=0;break;}}if(!temp)break;}ans=max(ans,cur);}printf("%lldn",ans);return 0;} 题目大意：给定一个无向图，现在你从点s出发，向其他点跑，路径一定选择最短路，问你一共跑k米，到达的点数的个数是多少？注意在路中间停下来也算点的个数。
n<=1e5，m<=1e5.
思路：直接dijkstra求出s到每个点的最短路的距离，然后你只需要思考一个问题：如果没有点恰好为k，那是不是所有的点都在边上？这时候直接统计；如果有点的距离恰好为k，那是否会引起计数的重复？如果你记录边的话，计数是绝对会重复的，所以再加一个重复个数的计数即可。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>#include <queue>using namespace std;const int maxn=1e5+10;int dis[maxn];struct HeapNode{ int u,d; HeapNode(int _u,int _d):u(_u),d(_d){} bool operator < (const HeapNode &rhs)const{ return d>rhs.d; }};int vis[maxn];struct Edge{ int u,v,cost; Edge(int u,int v,int cost):u(u),v(v),cost(cost){}};vector<int>G[maxn];vector<Edge>edges;void add_edges(int u,int v,int cost){ edges.push_back(Edge(u,v,cost)); edges.push_back(Edge(v,u,cost)); int sz=edges.size(); G[u].push_back(sz-2); G[v].push_back(sz-1);}const int INF=1e9;int n,m,k;void Dijkstra(int s){ memset(vis,0,sizeof(vis)); for(int i=0;i<=n;i++)dis[i]=INF; dis[s]=0; vis[s]=1; priority_queue<HeapNode>Q; Q.push(HeapNode(s,0)); while(Q.size()){ HeapNode x=Q.top();Q.pop(); int u=x.u; for(int i=0;i<G[u].size();i++){ Edge &e=edges[G[u][i]]; int v=e.v; if(dis[v]>dis[u]+e.cost){ dis[v]=dis[u]+e.cost; if(!vis[v]){ vis[v]=1; Q.push(HeapNode(v,dis[v])); } } } }}signed main(){ int s; scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=m;i++){ int u,v,cost; scanf("%d%d%d",&u,&v,&cost); add_edges(u,v,cost); } scanf("%d",&k); Dijkstra(s); int ans=0; int cnt=0; for(int u=1;u<=n;u++){ if(dis[u]==k)ans++; for(int i=0;i<G[u].size();i++){ Edge &e=edges[G[u][i]]; if(dis[u]<k&&dis[u]+e.cost>k&&(dis[e.v]>k||k<=e.cost-(k-dis[u])+dis[e.v])){ ans++; if(k==e.cost-k+dis[u]+dis[e.v])cnt++; } } } printf("%dn",ans-cnt/2); return 0;}/*3 3 11 2 22 3 31 3 44*/ 题目大意：给定一个01数组，现在支持两种操作
1.将整个区间01翻转
2.询问整个大区间的最长不递减子序列长度。
思路：经典线段树维护最长递增子序列，考烂的题目，然而没有时间看。。。
线段树维护左边区间开头0的个数，右边区间开头0的个数，区间0的个数与1的个数。
然后只需要考虑合并时的贡献，可以参考一下HDU6404这个题，把高低看成0和1，就是这个题了，合并很简单的。
#include<bits/stdc++.h>using namespace std;#define all(a) a.begin(),a.end()int n,m;const int maxn=1e5+10;int a[maxn];struct node{int l,r;int r0=0,l0=0,a1=0,a0=0;int lazy=0;}t[maxn<<2];void build(int u,int l,int r){t[u].l=l,t[u].r=r;if(l==r){t[u].l0=t[u].r0=1;if(a[l]==1){t[u].a1=1;t[u].a0=0;}else {t[u].a1=0;t[u].a0=1;}return;}int mid=(l+r)/2;build(u<<1,l,mid);build(u<<1|1,mid+1,r);t[u].l0=max(t[u<<1].a0+t[u<<1|1].l0,t[u<<1].l0+t[u<<1|1].a1);t[u].a0=t[u<<1].a0+t[u<<1|1].a0;t[u].r0=max(t[u<<1|1].a0+t[u<<1].r0,t[u<<1|1].r0+t[u<<1].a1);t[u].a1=t[u<<1|1].a1+t[u<<1].a1;}int solve(){cout<<max(t[1].l0,max(t[1].a1,t[1].a0))<<endl;return 0;}void upd(int u){t[u<<1].lazy=!t[u<<1].lazy;t[u<<1|1].lazy=!t[u<<1|1].lazy;swap(t[u<<1].l0,t[u<<1].r0);swap(t[u<<1].a0,t[u<<1].a1);swap(t[u<<1|1].l0,t[u<<1|1].r0);swap(t[u<<1|1].a0,t[u<<1|1].a1);}void upd(int u,int L,int R){int l=t[u].l,r=t[u].r;if(l==L&&r==R){t[u].lazy=!t[u].lazy;swap(t[u].l0,t[u].r0);swap(t[u].a0,t[u].a1);return;}if(t[u].lazy){t[u].lazy=0;upd(u);}int mid=(l+r)/2;if(R<=mid)upd(u<<1,L,R);else if(L>mid)upd(u<<1|1,L,R);else upd(u<<1,L,mid),upd(u<<1|1,mid+1,R);t[u].l0=max(t[u<<1].a0+t[u<<1|1].l0,t[u<<1].l0+t[u<<1|1].a1);t[u].a0=t[u<<1].a0+t[u<<1|1].a0;t[u].r0=max(t[u<<1|1].a0+t[u<<1].r0,t[u<<1|1].r0+t[u<<1].a1);t[u].a1=t[u<<1|1].a1+t[u<<1].a1;}signed main() {ios::sync_with_stdio(false);cin.tie(NULL);cin>>n>>m;for(int i=1;i<=n;++i){char tmp;cin>>tmp;a[i]=tmp-'0';}build(1,1,n);while(m--){char q;cin>>q;if(q=='q')solve();else{int l,r;cin>>l>>r;upd(1,l,r);}}return 0;}/*5 510011qc 1 5qc 1 3q*/