链接
1.括号序列贪心/CF&51nod原题
【分析】：
贪心，每次到i的时候，假如你要在i里面要卖掉股票，获益是a[i], 肯定要在前面要么：1）把已经卖了的变成不买不卖，需要-a[j]， 2）把已经不买不卖的变成买，需要-a[j]
【原题链接】：CF&E
CF&D
51nod高卖低买
3.构造/封闭运算/费马小定理下模意义/重新定义＋和 *
【题意】：
输入：素数p
要求构造规则a[p*p]，使其满足：(m+n)^p=m^p+n^p
a的含义：
a[i][j] = (i-1) + (j-1)，a[p+i][j] = (i-1) * (j-1)
【 + 意义】加法全0
【 * 意义】
【分析】：（转载自 http://www.cnblogs.com/xiuwenli/p/9534918.html）
给定的p是素数，要求给定一个加法运算表和乘法运算表，使(m+n)p=mp+np(0≤m,n<p)。
因为给定的p是素数，根据费马小定理得 (m+n)p−1≡1(mod p)
因此，(m+n)p≡m+n (mod p),
同时，mp+np≡m+n (mod p)。
所以在模p意义下，(m+n)p=mp+np(0≤m,n<p) 恒成立，且加法运算与乘法运算封闭。
等式两边%p，发现左右都是n+m。等式成立，所以所需的加法群和乘法群就很明显
就是%p意义下的加法群和乘法群。
4.费马大定理/勾股数定理/15浙工大校赛原题
【原题链接】n==2的情况
Codeforces Round #368 (Div. 2)C. Pythagorean Triples
给出一个整数问是否能找出另外两个数使得构成一组勾股数。如不能则输出-1，反之，则输出任意符合的两个数。
7.分组后单调队列/倍增/线段树
9.子树/树形dp与阶乘/dfs/结论题
10.树状数组/线段树优化dp
【1001】
#include <iostream>
#include <cstdio>
#include <queue>
#include <set>
#include <cstring>
using namespace std;
typedef long long ll;
multiset<pair<int,bool> > st;
const int maxn = 1e5 + 4;
int t, n, a;
int main()
{//freopen("input.txt", "r", stdin);//freopen("output.txt", "w", stdout);int t;scanf("%d", &t);while(t--){st.clear();ll ans = 0;int cnt = 0;scanf("%d", &n);for(size_t i = 0; i < n; i++){ll a;scanf("%lld", &a);if(!st.empty()&&(*st.begin()).first<a){ans += (a - (*st.begin()).first);if((*st.begin()).second==true)cnt++;st.erase(st.begin());st.insert(make_pair(a, true));st.insert(make_pair(a, false));}else{st.insert(make_pair(a, true));}}printf("%lld %d\n", ans, cnt * 2);}return 0;
}【1003】
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;int main()
{int T;scanf("%d", &T);for(int ti=0;ti<T;ti++){int p;scanf("%d", &p);for (int i = 0; i < p; i++){for (int j = 0; j < p; j++){if (j)printf(" ");printf("%d", (i + j) % p);}printf("\n");}for (int i = 0; i < p; i++){for (int j = 0; j < p; j++){if (j)printf(" ");printf("%d", (i*j) % p);}printf("\n");}}
}【1004】
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;int main()
{int t;scanf("%d", &t);while (t--){ll a, n;scanf("%lld%lld", &n, &a);if (n > 2)printf("-1 -1\n");else{if (n == 0)printf("-1 -1\n");else if (n == 1)printf("%lld %lld\n", 1, a + 1);else if (n == 2){if (a & 1){ll x = (a - 1) / 2;ll c = x*x + (x + 1)*(x + 1);printf("%lld %lld\n", c - 1, c);}else{ll x = a / 2;printf("%lld %lld\n", x*x - 1, x*x + 1);}}}}
}【1007-单调队列】
#include <bits/stdc++.h>
using namespace std;int a[10010];
int n,m,k;
long long s;
long long ans;
bool vis[10010];
long long sum[30010];
int b[30010];
void gao(vector<int> vec) {int sz = vec.size();sum[0] = 0;for (int i = 1; i < 3*sz; i++) {sum[i] = sum[i-1] + a[vec[(i-1)%sz]];}long long s1 = 0;long long tt = m/sz-1;if (tt < 0) tt = 0;s1 = tt*sum[sz];if (s1 < 0) s1 = 0;int lm = m - tt*sz;long long ms = 0;int st, ed;st = 0; ed = 0;b[ed++] = 0;for (int i = 1; i < 3*sz; i++) {while (st < ed && b[st] < i - lm)st++;ms = max(ms, sum[i] - sum[b[st]]);while (st < ed && sum[b[ed-1]] >= sum[i])ed--;b[ed++] = i;}ans = min(ans, max(0LL, s - s1 - ms));
}int main() {int T;scanf("%d", &T);int iCase = 0;while (T--) {iCase++;cin>>n>>s>>m>>k;for (int i = 0; i < n; i++)scanf("%d", &a[i]);ans = s;memset(vis, false, sizeof(vis));for (int i = 0; i < n; i++) {if (vis[i])continue;vector<int>vec;int now = i;vec.push_back(i);vis[now] = true;now = (now+k)%n;while (now != i) {vec.push_back(now);vis[now] = true;now = (now+k)%n;}gao(vec);}printf("Case #%d: ", iCase);cout<<ans<<endl;}return 0;
}【线段树】
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const ll maxn = 4e4+7;
struct Segment_tree
{struct Node{ll Max;ll Size,son[2];void init(){son[0]=son[1]=Size=Max=0;}} T[maxn*4];ll cnt,root;void init(ll l,ll r,ll *a){cnt=0;root=build(l,r,a);}inline void update(ll pos){if(T[pos].Size==1)return ;T[pos].Max=max(T[T[pos].son[0]].Max,T[T[pos].son[1]].Max);}inline ll build(ll l,ll r,ll *a){ll pos=++cnt;T[pos].init();T[pos].Size=r-l+1;if(l==r){T[pos].Max=a[l];return pos;}ll mid=(l+r)>>1;T[pos].son[0]=build(l,mid,a);T[pos].son[1]=build(mid+1,r,a);update(pos);return pos;}void cov(ll L,ll R,ll i,ll v,ll pos=1){if(L==R){T[pos].Max=max(T[pos].Max,v);return ;}ll mid=(L+R)>>1;if(i<=mid)cov(L,mid,i,v,T[pos].son[0]);elsecov(mid+1,R,i,v,T[pos].son[1]);update(pos);}ll query_Max(ll L,ll R,ll l,ll r,ll pos=1){if(l>r)return 0;if(L==l&&R==r){return T[pos].Max;}ll mid=(L+R)>>1;if(r<=mid)return query_Max(L,mid,l,r,T[pos].son[0]);else if(l>mid)return query_Max(mid+1,R,l,r,T[pos].son[1]);elsereturn max(query_Max(L,mid,l,mid,T[pos].son[0]),query_Max(mid+1,R,mid+1,r,T[pos].son[1]));}
}tree;
ll a[maxn],ans;
ll n,s,m,k;
bool vis[maxn];
ll p[maxn],sum[maxn];
ll solve(ll start){ll sz=0;for(ll i=start;!vis[i];i=(i+k)%n){vis[i]=1;p[++sz]=i;}for(ll i=sz+1;i<=sz*4;i++){p[i]=p[i-sz];}for(ll i=1;i<=sz*4;i++)sum[i]=sum[i-1]+a[p[i]];tree.init(1,sz*4,sum);for(ll i=1;i<=sz;i++){if(m<=sz){ll sm=tree.query_Max(1,sz*4,i,i+m-1)-sum[i-1];ans=max(ans,sm);}else {if(sum[sz]<=0){ll sm=tree.query_Max(1,sz*4,i,i+(m%sz)+sz-1)-sum[i-1];ans=max(ans,sm);}else {ll sm=sum[sz]*((m/sz)-1)+tree.query_Max(1,sz*4,i,i+(m%sz)+sz-1)-sum[i-1];ans=max(ans,sm);}}}
}
int main(){ll t;scanf("%I64d",&t);for(ll cas=1;cas<=t;cas++){memset(vis,0,sizeof(vis));ans=0;scanf("%I64d%I64d%I64d%I64d",&n,&s,&m,&k);for(ll i=0;i<n;i++)scanf("%I64d",a+i);for(ll i=0;i<n;i++){if(!vis[i]){solve(i);}}printf("Case #%I64d: %I64d\n",cas,max(0ll,s-ans));}return 0;
}【倍增】
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define debug(x) cerr<<#x<<" = "<<(x)<<endl
#define eps 1e-8
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int MAXN=(int)1e4+5;
const int MOD=(int)1e9+7;
struct node{ll a,b;node(){}node(ll x){b=x;a=max(x,0ll);}node operator + (const node &p)const{node re;re.b=b+p.b;re.a=max(a,b+p.a);return re;}
};
node a[MAXN][33];
int nxt[MAXN][33];
node cal(int x,int y){int k=0;node re=node(0);while(y){if(y&1){re=re+a[x][k];x=nxt[x][k];}k++;y>>=1;}return re;
}int main()
{int t;scanf("%d",&t);for(int ca=1;ca<=t;ca++){int n,m,k;ll s;scanf("%d%lld%d%d",&n,&s,&m,&k);for(int i=0;i<n;i++){int x;scanf("%d",&x);a[i][0]=node(x);nxt[i][0]=(i+k)%n;}for(int j=1;(1<<j)<=m;j++){for(int i=0;i<n;i++){a[i][j]=a[i][j-1]+a[nxt[i][j-1]][j-1];nxt[i][j]=nxt[nxt[i][j-1]][j-1];}}ll ans=s;for(int i=0;i<n;i++){node tmp=cal(i,m);ans=min(ans,max(0ll,s-tmp.a));}printf("Case #%d: %lld\n",ca,ans);}return 0;
}【1009】
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
const ll mod = 1e9+7;
struct node
{int x,y,v,nxt;
}edge[maxn<<1];
ll head[maxn],cnt,n;
ll sz[maxn];
ll an;
int add(int x,int y,int v)
{edge[cnt].x=x;edge[cnt].y=y;edge[cnt].v=v;edge[cnt].nxt=head[x];head[x]=cnt++;
}
int dfs(int root,int fa)
{sz[root]=1;for(int i=head[root]; i!=-1; i=edge[i].nxt){int a=edge[i].y;int b=edge[i].v;if(a==fa) continue;dfs(a,root);sz[root] += sz[a];an = ( an + (n-sz[a])%mod * sz[a]%mod * b%mod )%mod;}
}
ll fac[maxn];
int main()
{while(~scanf("%d",&n)){fac[0]=1;for(int i=1;i<=maxn;i++)fac[i]=(fac[i-1]*i)%mod;//阶乘取余打表an=0;memset(head,-1,sizeof(head));memset(sz,0,sizeof(sz));cnt=0;for(int i=1;i<=n-1;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}dfs(1,-1);printf("%lld\n",(ll)(2*an%mod*fac[n-1]%mod)%mod);}
}【1010】
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<cstdlib>
#include<cmath>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 1000000000;
const int maxn = 123456;
int T, n, m;
int tot, ans;
int maxs[maxn * 4];
struct Node
{int x, y;int val;int idd;
}nod[maxn];int cmp1(Node a, Node b)
{if (a.y != b.y)return a.y<b.y;elsereturn a.x<b.x;
}int cmp2(Node a, Node b)
{if (a.x != b.x)return a.x<b.x;elsereturn a.y>b.y;
}void Pushup(int rt)
{maxs[rt] = max(maxs[rt * 2], maxs[rt * 2 + 1]);
}void Build(int l, int r, int rt)
{if (l == r){maxs[rt] = 0;return;}int m = (l + r) / 2;Build(l, m, rt * 2);Build(m + 1, r, rt * 2 + 1);Pushup(rt);
}void Update(int pos, int l, int r, int k, int rt)
{if (l == r){maxs[rt] = k;return;}int m = (l + r) / 2;if (pos <= m)Update(pos, l, m, k, rt * 2);elseUpdate(pos, m + 1, r, k, rt * 2 + 1);Pushup(rt);
}int QueryMax(int L, int R, int l, int r, int rt)
{if (R == 0)return 0;if (l >= L&&r <= R)return maxs[rt];int m = (l + r) / 2;int ret = -INF;if (L <= m)ret = max(ret, QueryMax(L, R, l, m, rt * 2));if (R>m)ret = max(ret, QueryMax(L, R, m + 1, r, rt * 2 + 1));return ret;
}int main()
{scanf("%d", &T);while (T--){ans = -INF;tot = 1;scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d%d%d", &nod[i].x, &nod[i].y, &nod[i].val);sort(nod + 1, nod + n + 1, cmp1);nod[1].idd = tot++;//离散化for (int i = 2; i <= n; i++){if (nod[i].y == nod[i - 1].y)nod[i].idd = nod[i - 1].idd;elsenod[i].idd = tot++;}sort(nod + 1, nod + n + 1, cmp2);Build(1, n, 1);for (int i = 1; i <= n; i++){int x = QueryMax(1, nod[i].idd - 1, 1, n, 1);ans = max(x + nod[i].val, ans);Update(nod[i].idd, 1, n, x + nod[i].val, 1);}printf("%d\n", ans);}return 0;
}
