A.鬥牛ios
給定五個0~9範圍內的整數a1,a2,a3,a4,a5。若是能從五個整數中選出三個而且這三個整數的和爲10的倍數（包括0），那麼這五個整數的權值即爲剩下兩個沒被選出來的整數的和對10取餘的結果，顯然若是有多個三元組滿 和是10的倍數，剩下兩個數之和對10取餘的結果都是相同的；若是選不出這樣三個整數，則這五個整數的權值爲-1。數組
如今給定T組數據，每組數據包含五個0~9範圍內的整數，分別求這T組數據中五個整數的權值。函數
【輸入格式】ui
第一行一個整數T(1<=T<=1000)，表示數據組數。spa
接下來T行，每行5個0~9的整數，表示一組數據。code
【輸出格式】排序
輸出T行，每行一個整數，表示每組數據中五個整數的權值。隊列
【樣例輸入】string
4it
1 0 0 1 0
1 0 0 8 6
3 4 5 6 7
4 5 6 7 8
【樣例輸出】
2
-1
-1
0
5個數裏面選3個，C53也就10種，實在不行暴力也能夠，固然也能夠用dfs
找到那就剪枝退出。
代碼：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int num[6],all,ans;
bool vis[6];
bool finding;
void dfs(int now,int start);
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
memset(vis,0,sizeof(vis));
ans=-1;
finding=false;
for(int i=1;i<=5;i++) scanf("%d",&num[i]),all+=num[i];
dfs(0,1);
printf("%d\n",ans);
}
}
void dfs(int now,int start)
{
if(finding)
return ;
if(now==3)
{
int temp1=0,temp2=0;
for(int i=1;i<=5;i++)
if(vis[i]) temp1+=num[i];
else
temp2+=num[i];
if(temp1%10==0)
finding=true,ans=temp2%10;
return ;
}
for(int i=start;i<=5;i++)
{
if(vis[i]) continue;
else
{
vis[i]=true;
dfs(now+1,i+1);
vis[i]=false;
}
}
}
B.打地鼠
給定n個整數a1,a2,...,an和 一個d，你須要選出若 幹個整數，使得將這些整數從小到大 排好序以後，任意兩個相鄰的數之差都不 小於給定的d，問最多能選多少個數出來。
【輸入格式】
第一行兩個整數n,d(1<=n<=10^5,0<=d<=10^9)，分別表示整數個數和相鄰整數差的下界。
第二行n個整數a1,a2,...,an(1<=ai<=10^9,1<=i<=n)，表示給定的n個整數。
【輸出格式】
僅 一行一個整數，表示答案。
【樣例輸入】
6 2
1 4 2 8 5 7
【樣例輸出】
3
此題是個貪心，先將輸入的數字排個序，貪心尋找只要間距大於等於d那就加上去
代碼：
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> object;
int main()
{
int n,d,ans,now,num;
while(scanf("%d%d",&n,&d)!=EOF)
{
object.clear();
now=0;
ans=1;
for(int i=0;i<n;i++)
scanf("%d",&num),object.push_back(num);
sort(object.begin(),object.end());
for(int i=1;i<object.size();i++)
{
if(object[i]-object[now]>=d)
ans++,now=i;
}
printf("%d\n",ans);
}
}
C.排隊打飯
下課了，有n位同窗陸續趕到食堂進行排隊打飯，其中第i位同窗的到達時間爲ai，打飯耗時爲ti，等待時間上限爲bi，即若是其在第ai+bi秒的時刻仍然沒有輪到他開始打飯，那麼他將離開打飯隊列另尋吃飯的地 。問每位同窗的開始打飯時間，或者指出其提早離開了隊伍（若是這樣則輸出-1）。
【輸入格式】
第一行一個整數n(1<=n<=10^5)，表示來打飯的同窗數量。
接下來n ，每行三個整數ai,ti,bi(1<=ai,ti,bi<=10^9,1<=i<=n)，分別表 每位同窗的到達時間、打
飯耗時、等待時間上限。
保證a1<a2<...<an
【輸出格式】
n個整數，表 每位同窗的開始打飯時間或者-1（若是該同窗提早離開了隊伍）。
【樣例輸 】
4
1 3 3
2 2 2
3 9 1
4 3 2
【樣例輸出】
1 4 -1 6
由於輸入就是ai<a(i+1)因此都不須要排序了，直接模擬順序處理，記錄當前時間time
若是time大於這個同窗最後等待時間那就輸出-1，不然取time和他到達食堂時間的最大值。
模擬就能夠了
代碼：
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn=1e5+100;
int a[maxn],b[maxn],c[maxn];
int main()
{
int n,time;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d%d%d",&a[i],&b[i],&c[i]),c[i]=a[i]+c[i];
time=a[1];
for(int i=1;i<=n;i++)
{
if(i!=1)
printf(" ");
if(time>c[i]) printf("-1");
else
{
printf("%d",max(time,a[i]));
time=max(time,a[i])+b[i];
}
}
printf("\n");
}
return 0;
}
D.二叉搜索樹
給定 個1~n的排列P，即長度爲n，且1~n中全部數字都剛好出現一次的序列。如今按順序將排列中的元素一一插入到初始爲空的 二叉搜索樹中（左小右大），問最後每一個節點的父親節點的元素是什麼。特別地，根節點的 親節點元素視爲0。
【輸入格式】
第一行一個整數n(1<=n<=10^5)，表示排列P中的元素個數。
第二行n個整數p1,p2,...,pn(1<=pi<=n,1<=i<=n)，表示給定的排列。
【輸出格式】
一行n個整數，其中第i個整數ai表示元素i對應節點的父親節點的元素。特別地，根節點的父親節點元素視爲0。
5
2 3 5 1 4
【樣例輸出】
2 0 2 5 3
一開始直接建樹，等到5點左右系統恢復提交tle，纔想起n=1e5退化成鏈的時候就成O(n^2)了
後來換了個區間最值查詢的方法，我用的線段樹，寫完的時候都不能提交了（也不知道可否ac），不過期間複雜度O(n*logn)應該差很少了
大體方法是這樣的好比 5個點，2，3，5，1，4，從左往右循環，遇到2了，而後查詢值爲1到（2-1）的這些節點裏面第一個出現的點，這裏是1，那麼father[1]=2,而後標記vis[1]=true;而且更新線段樹，time[1]=INF，再查詢(2+1)到5這裏找出來是3，那麼father[3]=1,而後標記vis[3]=true;接下來i=2，節點值是3，因爲i點和找出來的左右節點都找出來了，因此都標記vis和更新。查詢1到2 （由於節點值1和2都已經標記了，因此節點值3沒有左子樹），接下來找（4-5）返回了5，由於5出如今4前面，
因而father[5]=3,而後標記3和5（更新vis和更新線段樹），而後i=3，值爲5，查詢1到4，這裏1,2,3都標記過了只有4，因此father[4]=5,再查詢6到5（固然是沒有的，因此結點值5沒有右子樹），到此爲止，全部點都標記了，循環後面也不會更新father了。
這個代碼有誤的話歡迎指出！
代碼：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e5+100;
int time[maxn];
int num[maxn];
const int INF=0x3f3f3f3f;
struct Segtree
{
int val;
};
Segtree tree[maxn*5];
bool vis[maxn];
int father[maxn];
void build(int root,int l,int r);
void update(int root,int l,int r,int index,int val);
int query(int root,int l,int r,int ql,int qr);
int main()
{
int n;
time[0]=INF;
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++) scanf("%d",&num[i]),time[num[i]]=i;
build(1,1,n);
memset(vis,0,sizeof(vis));
memset(father,0,sizeof(father));
for(int i=1;i<=n;i++)
{
vis[num[i]]=true;
int now1=query(1,1,n,1,num[i]-1);
int now2=query(1,1,n,num[i]+1,n);
if(now1&&!vis[now1])
father[now1]=num[i],update(1,1,n,now1,INF),vis[now1]=true;
if(now2&&!vis[now2])
father[now2]=num[i],update(1,1,n,now2,INF),vis[now2]=true;
update(1,1,n,num[i],INF);
}
for(int i=1;i<=n;i++)
{
if(i!=1) printf(" ");
printf("%d",father[i]);
}
printf("\n");
}
return 0;
}
void build(int root,int l,int r)
{
if(l==r)
tree[root].val=l;
else
{
int mid=(l+r)/2;
build(root*2,l,mid);
build(root*2+1,mid+1,r);
tree[root].val=time[tree[root*2].val]<time[tree[root*2+1].val]?tree[root*2].val:tree[root*2+1].val;
}
}
int query(int root,int l,int r,int ql,int qr)
{
if(qr<l||ql>r)
return 0;
if(ql<=l&&qr>=r)
return tree[root].val;
int mid=(l+r)/2;
int now1=query(root*2,l,mid,ql,qr);
int now2=query(root*2+1,mid+1,r,ql,qr);
return time[now1]<time[now2]?now1:now2;
}
void update(int root,int l,int r,int index,int val)
{
if(l==r)
time[tree[root].val]=val;
else
{
int mid=(l+r)/2;
if(index<=mid)
update(root*2,l,mid,index,val);
else
update(root*2+1,mid+1,r,index,val);
tree[root].val=time[tree[root*2].val]<time[tree[root*2+1].val]?tree[root*2].val:tree[root*2+1].val;
}
}
E.序列
給定一個長爲n的序列A，其中序列中的元素都是0~9之間的整數，對於一個長度一樣爲n整數序列B，定義其權值爲|A_i-B_i|(1<=i<=n)之和加上(B_j-B_j+1)^2(1<=j<n)之和。求全部長爲n的整數序列中，權值最小的序列的權值是多少。
【輸入格式】
第一行一個整數n(1<=n<=10^5)，表示序列A的長度。
第二行n個整數a1,a2,...,an(0<=ai<=9,1<=i<=n)，表示序列A中的元素。
【輸出格式】
【樣例輸入 】
6
1 4 2 8 5 7
【樣例輸出】
11
【解釋】
A數組是[142857]
B數組能夠是[344556]。
權值爲|A_i-B_i|(1<=i<=n)之和加上(B_j-B_j+1)^2(1<=j<n)之和。
權值第 部分|A_i-B_i|(1<=i<=n)之和爲：
|1-3|+|4-4|+|2-4|+|8-5|+|5-5|+|7-6|=2+0+2+3+0+1=8
權值第 部分(B_j-B_j+1)^2(1<=j<n)之和爲：
(3-4)^2+(4-4)^2+(4-5)^2+(5-5)^2+(5-6)^2=1+0+1+0+1=3
因此總權值爲8+3=11。
分析：
思考下，對於b數組每一個值的選取對答案的貢獻是什麼？？其實只有前
一個把，由於貢獻只不過是加上它和它前一個值的差值的平方，和它和A數組對應位置的
差值絕對值，因此我們就維護一個now數組,now[i]表示的是當前結束的B的這個
位置值爲i，那麼更新就須要前一個位置的0-9種狀況取最優，那麼複雜度就是
O(10*10*n)，n=1e5,那麼差很少1秒內了
代碼：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int tp1[10][10],tp2[10][10];
int now[10],now_temp[10]; //目前結尾爲i的最小函數值，複雜度O(n*10*10)約等於1e7，差很少一秒
const int INF=0x3f3f3f3f;
void init();
int main()
{
int n,num;
init();
while(scanf("%d",&n)!=EOF)
{
memset(now,0,sizeof(now));
for(int i=0;i<n;i++)
{
scanf("%d",&num);
for(int j=0;j<10;j++)
{
int temp=INF;
for(int k=0;k<10;k++)
{
int tp;
if(i)
tp=now[k]+tp1[j][num]+tp2[j][k];
else
tp=now[k]+tp1[j][num];
if(tp<temp) temp=tp;
}
now_temp[j]=temp;
}
for(int i=0;i<10;i++) now[i]=now_temp[i];
}
int ans=INF;
for(int i=0;i<10;i++)
ans=min(ans,now[i]);
printf("%d\n",ans);
}
return 0;
}
void init()
{
for(int i=0;i<10;i++)
for(int j=0;j<10;j++)
{
tp1[i][j]=i<j?(j-i):(i-j);
tp2[i][j]=(i-j)*(i-j);
}
}
題不算很難，細節很重要！