題目：http://www.ifrog.cc/acm/contest/1013 官方題解：http://www.ifrog.cc/acm/solution/16
直接貼上了，沒過的題以后再補（盡管不太可能QAQ）
第一題、直接枚舉所有可能的x并且計算答案，得出最優解 【水題，忽略】
第二題、可以連接的兩個工廠相當于可以匹配的兩個點，那么問題轉化為求兩個串的最長公共子序列，但O(n^2)的復雜度會超時，由于第二個串每個點最多只有6個點與之匹配，所以可以把第二個串的每個點變成可以與之匹配的六個編號從大到小排序，然后求最長上升子序列。
【這種套路題還是見過些的】
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int N=1e6+9;const int INF=1e9+7;int g[N],d[N],a[N],k[11];int n;int main() { //freopen("in.txt","r",stdin); while(~scanf("%d",&n)) { int ans=0,cnt=0; for(int i=1; i<=n; i++)g[i]=INF; for(int i=0; i<n; i++) { for(int j=0; j<6; j++) { scanf("%d",&k[j]); } sort(k,k+6); for(int j=5;j>=0;j--)a[cnt++]=k[j]; } for(int i=1;i<=cnt;i++)g[i]=INF; for(int i=0;i<cnt;i++){ int k=lower_bound(g+1,g+n+1,a[i])-g; d[i]=k; g[k]=a[i]; ans=max(ans,d[i]); } cout<<ans<<endl; } return 0;}第三題、當一課排序二叉樹建立起來之后我們可以發現，從某個點x往上走，第一個往左的節點的值是在x前插入的小于x的最大值，第一個往右的值是在x前插入的大于x的最小值，所以x所在的層數就是在插入x之前比x大的最小值的層數和比x小的最大值的層數中，較大值加一，若把問題反過來看，不是插入而是從二叉樹中把一個個點拿走，那么可以很簡單地用并查集找到上述的兩個值。
【講真，這題挺不錯的（雖然沒做出來），還是可以做的】
第四題、由于x經過一次函數調用f(x)之后不超過9^3，所以直接找循環節即可。 【水題略過】
第五題、先對原串st做一次kmp，然后做動態規劃f[i][j]表示長度為i的字符串中不存在子串為st并且所有后綴中與st的前綴匹配的最長長度為j，然后枚舉第i＋1位的字符，如果等于st[j+1]的話那么轉移到f[i+1][j+1],否則轉移到f[i][k]，其中k由kmp算法計算得到。
【這題自己一開始想錯了，瘋狂WA，沒做出來QAQ】
#include<bits/stdc++.h>using namespace std;typedef long long ll;const int mod=1e9+7;const int N=1000+7;char ch, s[N];int dp[N][N], c[N][156], nex[N];int main() { int n, m, i, j, p, q, ans; //freopen("in.txt","r",stdin); while(~scanf("%d%d", &n, &m)) { scanf("%s",s+1); memset(dp, 0, sizeof(dp)); p = 0, q = 1, nex[1] = 0; while(q<=m) { if(p==0 || s[p]==s[q]) { nex[++q] = ++p; } else p = nex[p]; } for(i=1; i<=m; i++) { for(ch='a'; ch<='z'; ch++) { int p = i; while(p!=0 && s[p]!=ch) p = nex[p]; c[i][ch] = p; //第六題、只要判斷兩個：1、所有對角線連接的端點顏色都不一樣；2、所有線段都不想交。
【哇~~，題解好簡單啊（一開始沒看到相鄰兩點顏色不同，還想了好一會兒 T_T）】
第七題、我們先計算出tornado的速度為v0，然后分類討論：1、如果v > v0那么肯定可以追上；2、如果v == v0，那么速度向量與（x1-x0, y1-y0）的夾角小于90度就可以追上；3、我們先假設可以追上，而且時間為t，那么追上時tornado走過的路程長度為t v0，Feigay走過的路程為t v，加上tornado和Feigay原始位置的距離，還有速度向量和(x1-x0, y1-y0)的夾角可以根據余弦定理列出方程，若有正數解那么可以追上。
【題解講的很清楚了，分情況討論即可】
第八題、可以先想到一個dp的方法f[i][j] = max{f[i-1][k] + A[i] + B[j] | k < j 且(i, j)可以匹配, f[i-1][j], f[i][j-1], f[i-1][j-1]}。可是這個dp是O(n^2)時間復雜度的，我們可以觀察轉移方程，發現求最大值的k其實是一段連續的值，所以可以利用選段樹或者樹狀數組進行優化，把復雜度降低成O(m * log n)。
【沒想過dp，一上來直接考慮樹狀數組啊】
#include<bits/stdc++.h>using namespace std;#define fi first#define se secondtypedef pair<int,int>pii;typedef long long ll;const int INF=0x3f3f3f3f;const int N=3000000+7;ll c[N],a[N],b[N];pii e[N];int cmp(const pii& a,const pii& b){ if(a.fi==b.fi)return a.se>b.se; return a.fi<b.fi;}int lowbit(int x){return x&(-x);}void add(int x,ll v){ for(int i=x;i<N;i+=lowbit(i))c[i]=max(c[i],v);}ll query(int x){ ll maxn=0; for(int i=x;i>0;i-=lowbit(i))maxn=max(maxn,c[i]); return maxn;}int main(){ //freopen("in.txt","r",stdin); int n,m; while(~scanf("%d%d",&n,&m)){ memset(c,0,sizeof(c)); for(int i=0;i<m;i++){ scanf("%d%d",&e[i].fi,&e[i].se); } for(int i=1;i<=n;i++)scanf("%lld",&a[i]); for(int i=1;i<=n;i++)scanf("%lld",&b[i]); sort(e,e+m,cmp); for(int i=0;i<m;i++){ int u=e[i].fi,v=e[i].se; ll t=query(v-1); add(v,t+a[u]+b[v]); } printf("%lld/n",query(n)); } return 0;}第九題、如果n大于6的時候結果肯定為0，因為每次a與b操作之后至少可以使a的1的數量減少一半，所以進行6次操作肯定可以使a變成0。當n小于等于6的時候，暴力枚舉每個數是否取反以及每個數之間的符號。
【看完題解恍然大悟啊QAQ，因為a和b或者~b相與，至少可以使a的數量減少一半，那么進行6次以上肯定是0了。相與6直接暴力。另外，其實或，異或沒啥用（或是真的沒用，異或可以用~和&代替】
#include<bits/stdc++.h>using namespace std;typedef unsigned long long ll;const int N=1e6+9;const int INF=1e9+7;ll a[N], ans;int n;void dfs(int x, ll now) { if (x == n) { ans = min(ans, now); return; } dfs(x+1, now & a[x]); dfs(x+1, now & ~a[x]);}int main() { while (~scanf("%d", &n)) { for (int i = 0; i < n; ++i) { scanf("%llu", &a[i]); } if (n > 6) { printf("0/n"); continue; } else { ans = ~(0ll); dfs(1, ~a[0]); dfs(1, a[0]); printf("%llu/n", ans); } } return 0;}第十題、先求出樹的dfs序，進入一個點以及離開一個點都在dfs序上有一個標記，然后每一條鏈和子樹上的操作都可以變成dfs序上的一段區間，把dfs序做成兩棵線段樹，黑白各一棵，黑點在白樹上值為0，白點在黑樹上值為0，進入點的值為正數，離開點的值為負數，那么對于一個翻轉操作就是把黑白樹對應的一段交換，打個標記就好，對于一次詢問，分成上升和下降兩段，上升取反跟下降的和加起來就是答案，注意最近公共祖先要特殊處理好。
【占坑待補】
新聞熱點
疑難解答
