1. 简单的数列
【问题描述】
一个简单的数列问题:
给定一个长度为 n 的数列,求数列中这样的三个元素 ai,aj,ak 的个数,满足 ai< aj > ak,
且 i<j<k 。
【输入】
第 1 行是一个整数 n(1<=n<=50000)
。
接下来 n 行,每行一个元素 ai(0 <= ai <= 32767)。
【输出】
一个数,满足 ai<aj>ak (i<j<k) 的个数。
【输入输出样例】
Input
5
1
2
3
4
1
Output
6
【数据范围】
对于 30%的输入数据有 n<=2000。
对于 80%的输入数据有 n<=10000。
对于 100%的输入数据有 n<=50000。
第一题，树状数组板子题
1 #define ll long long 2 #include<algorithm> 3 #include<iostream> 4 #include<iomanip> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cstdio> 8 #include<queue> 9 #include<ctime> 10 #include<cmath> 11 #include<stack> 12 #include<map> 13 #include<set> 14 15 using namespace std; 16 const int maxn=50010; 17 int C1[maxn],C2[maxn]; 18 int a[maxn],b[maxn]; 19 int c1[maxn],c2[maxn]; 20 int n; 21 void add1(int p,int x) { 22 while(p<=32768) { 23 C1[p]++; 24 p+= (p & (-p)); 25 } 26 } 27 void add2(int p,int x) { 28 while(p<=32768) { 29 C2[p]++; 30 p+=(p & (-p)); 31 } 32 } 33 int getsum1(int p) { 34 int sum=0; 35 while(p) { 36 sum+=C1[p]; 37 p-=(p & (-p)); 38 } 39 return sum; 40 } 41 int getsum2(int p) { 42 int sum=0; 43 while(p) { 44 sum += C2[p]; 45 p-=(p & (-p)); 46 } 47 return sum; 48 } 49 int main() { 50 freopen("queueb.in","r",stdin); 51 freopen("queueb.out","w",stdout); 52 cin>>n; 53 int i; 54 for(i=1; i<=n; i++) scanf("%d",&a[i]),a[i]++; 55 for(i=1; i<=n; i++) b[i]=a[n-i+1]; 56 for(i=1; i<=n; i++) { 57 add1(a[i],1); 58 int p=a[i]-1; 59 if(!p) continue; 60 c1[i]=getsum1(p); 61 } 62 for(i=1; i<=n; i++) { 63 add2(b[i],1); 64 int p=b[i]-1; 65 if(!p) continue; 66 c2[i]=getsum2(p); 67 } 68 int ll sum=0; 69 for(i=1; i<=n; i++) { 70 sum += (ll) c1[i] * (ll) c2[n-i+1]; 71 } 72 cout<<sum; 73 return 0; 74 }
- 2 -2. 黄金矿工
【问题描述】
黄金矿工是一个经典的小游戏,它可以锻炼人的反应能力。该游戏中,可以通过“挖矿”
获得积分并不断升级。玩家可以在线玩 flash 版黄金矿工,也可以下载后玩单机版黄金矿工。
目前,黄金矿工小游戏有多个版本,例如黄金矿工双人版,黄金矿工单人版等。
Jimmy 是一位黄金矿工,他所在的金矿是一个 n*n 的矩形区域(俯视),区域内有黄金、
石头和 TNT,由一个 n*n 的矩阵描述。黄金的价值对应矩阵中的正值,石头的价值对应矩阵
中的负值,TNT 由 0 表示。换句话说,挖到黄金赚钱,石头亏损,如果挖到 TNT 就挂了。
Jimmy 租到的挖矿工具很特别,它的形状是一个长宽任意(均为正整数)的矩形,可以
取走被该工具覆盖的矩形区域内的所有物品,但如果该区域内有 TNT,该工具将被炸毁,此
时 Jimmy 将不得不赔偿矿主+∞元!!
!需要注意的是,该工具只能在金矿范围内使用(即不
得超出金矿边界),且租金为每次使用十元。
现在,Jimmy 想知道,如果他至多只有一次租用该工具的机会,他能获得的最大收益是
多少。当然,如果 Jimmy 租用该工具无论如何都会亏损,他可以不租用,此时收益为 0.
【输入】
第一行:一个整数 n
接下来 n 行,每行 n 个整数(绝对值<100)
,为题目中所描述的矩阵。
【输出】
一个数,即 Jimmy 所能获得的最大收益。
【输入输出样例 1】
Input
3
0 -1 -1
0 -12 0
-19 0 0
Output
0
【样例解释】
无论 Jimmy 怎么挖矿,挖到的不是石头,就是 TNT,总之无论如何都会亏损,所以选择不租
用工具,收益为 0
【数据范围】
对于 30%的数据:0<n<=10
对于 60%的数据:0<n<=100
对于 100%的数据:0<n<=300
第二题，考场上没能写出来，。。。其实这个题要用到决策性优化，如果只有一列，则最大的值这样表示，f[i]表示以i结尾的 值最大的长条，设s[i]为前缀和，则f[i]=max(s[i]-s[k])(k<i)，即找到一个最小的k，这是一个决策。那么对于i来说，i 的前面最小的也是在k的时候取得最小，是一样的，所以i的决策就是i-1的决策，如果s[i] < s[k]，则把k置为i。回到这题，只是把一维变成了二维，使用二位前缀和，相当于还是一样的，只要枚举一下长度，矩阵的坐标，O(n^3)；
1 #define ll long long 2 #include<algorithm> 3 #include<iostream> 4 #include<iomanip> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cstdio> 8 #include<queue> 9 #include<ctime> 10 #include<cmath> 11 #include<stack> 12 #include<map> 13 #include<set> 14 #define SS system("pause"); 15 #define inf 3000000 16 using namespace std; 17 const int N=310; 18 int a[N][N],h[N][N]; 19 int n,ans=0; 20 void go_30() { 21 int i,j,k; 22 for(int len=1;len<=n;len++) { 23 for(i=n;i>=len;i--){ 24 k=0; 25 for(j=1;j<=n;j++){ 26 int op=h[i][k]-h[i-len][k]; 27 int now=h[i][j]-h[i-len][j]; 28 if(now<op) k=j; 29 else ans=max(ans,now-op); 30 } 31 } 32 } 33 } 34 int main() { 35 freopen("miner.in","r",stdin); 36 freopen("miner.out","w",stdout); 37 cin>>n;int i,j; 38 for(i=1;i<=n;i++) 39 for(j=1;j<=n;j++) { 40 scanf("%d",&a[i][j]); 41 if(!a[i][j]) a[i][j]=-inf; 42 h[i][j] = h[i][j-1]+a[i][j]; 43 } 44 for(i=2;i<=n;i++) 45 for(j=1;j<=n;j++) 46 h[i][j] += h[i-1][j]; 47 go_30(); 48 if(ans<=10) cout<<0; 49 else cout<<ans-10; 50 return 0; 51 }
- 3 -3. 旅行
【问题描述】
Z 小镇是一个景色宜人的地方,吸引来自各地观光客来此旅游观光。Z 小镇附近共有 N
个景点(编号为 1,2,3...N)
,这些景点被 M 条道路连接着,所有道路都是双向的,两个
景点之间可能有多条道路连接着。
也许是为了保护该地的旅游资源,Z 小镇有个奇怪的规定,就是对于一条给定的公路
Ri,任何在该公路上行驶的车辆速度必须为 Vi。速度变化太快使得游客们很不舒服,因此
从一个景点前往另一个景点的时候,大家都希望选择行使过程中最大速度和最小速度的比尽
可能小的路线,也就是所谓最舒适路线。
【输入】
第一行包括两个整数: N 和 M
接下来的 M 行每行包含三个正整数: x,y 和 v。表示景点 x 到景点 y 之间有一条双向
公路,车辆必须以速度 v 在该公路上行驶。
最后一行包含两个正整数 s,t,
表示想知道从景点 s 到景点 t 最大最小速度比最小的路径。
s 和 t 不可能相同。
【输出】
如果景点 s 到景点 t 没有路径,输出“IMPOSSIBLE”
。否则输出一个数,表示最小的速
度比。如果需要,输出一个既约分数。
【输入输出样例 1】
Input
4
1
3
1
2
2 1
4 2
4
【输入输出样例 2】
Input
3
1
1
2
1
3
2 10
2 5
3 8
3
【输入输出样例 3】
Input
3
1
2
1
2
2 2
3 4
3
Output
IMPOSSIBLE
Output
5/4
Output
2
因为只要的到最大值与最小值的比值，能有一条路径连通s,t即可，如果确定了最小值，只需要找到最小的最大值的边使得s，t连通，于是把边从小到大排序，从一到n枚举每一条边，设置他为最小边，在他后面按顺序加边，直到s与t连通，得到一个比值，不断更新答案即可；连通只要用并查集就行。
1 #include<algorithm> 2 #include<iostream> 3 #include<iomanip> 4 #include<cstring> 5 #include<cstdlib> 6 #include<cstdio> 7 #include<queue> 8 #include<ctime> 9 #include<cmath> 10 #include<stack> 11 #include<map> 12 #include<set> 13 #define inf 199999999 14 #define db double 15 using namespace std; 16 const int N=510,M=5010; 17 struct E{ 18 int to,net,w; 19 int fr; 20 }e[M*2]; 21 int n,m,num_e,head[N],s,t; 22 int fa[N]; 23 void add(int x,int y,int w) { 24 e[++num_e].to=y;e[num_e].net=head[x];e[num_e].w=w;head[x]=num_e;e[num_e].fr=x; 25 } 26 int gcd(int a,int b) { 27 return a%b==0? b :gcd(b,a%b); 28 } 29 int comp(const E &a,const E &b ){ 30 return a.w<b.w; 31 } 32 void init() { 33 for(int i=1;i<=n;i++) fa[i]=i; 34 } 35 int find(int x) { 36 if(x!=fa[x]) fa[x]=find(fa[x]); 37 return fa[x]; 38 } 39 void Union(int x,int y) { 40 fa[y]=x; 41 } 42 int main() { 43 freopen("comf.in","r",stdin); 44 freopen("comf.out","w",stdout); 45 memset(head,-1,sizeof(head)); 46 cin>>n>>m;int i; 47 int a,b; 48 a=inf;b=1; 49 for(i=1;i<=m;i++) { 50 int x,y,w;scanf("%d%d%d",&x,&y,&w); 51 add(x,y,w); 52 } 53 cin>>s>>t; 54 sort(e+1,e+m+1,comp); 55 for(i=1;i<=m;i++) { 56 init();int j; 57 int minn=e[i].w; 58 for(j=i;j<=m;j++){ 59 int r1=find(e[j].fr),r2=find(e[j].to); 60 if(r1!=r2) { 61 Union(r1,r2); 62 63 } 64 // printf("%d %d ",r1,r2); 65 if(find(s)==find(t)) break; 66 } 67 if(j>m) break; 68 if((db)e[j].w/(db)minn<(db)a/(db)b) a=e[j].w,b=minn; 69 } 70 int c=gcd(a,b); 71 a/=c,b/=c; 72 if(a==inf) { 73 puts("IMPOSSIBLE");return 0; 74 } 75 if(b==1) printf("%d",a); 76 else printf("%d/%d",a,b); 77 return 0; 78 }
【数据范围】
0<N<=500;0<M<=5000;
- 4 -4. 奶牛跑步
【问题描述】
Bessie 准备用从牛棚跑到池塘的方法来锻炼. 但是因为她懒,她只准备沿着下坡的路跑
到池塘,然后走回牛棚.
Bessie 也不想跑得太远,所以她想走最短的路经. 农场上一共有 M(1<=M<=10,000)条路,
每条路连接两个用 1..N(1<=N<=1000)标号的地点. 更方便的是,如果 X>Y,则地点 X 的高度大
于地点 Y 的高度. 地点 N 是 Bessie 的牛棚;地点 1 是池塘.
很快, Bessie 厌倦了一直走同一条路.所以她想走不同的路,更明确地讲,她想找出
K(1<=K<=100)条不同的路经.为了避免过度劳累,她想使这 K 条路径为最短的 K 条路径.
请帮助 Bessie 找出这 K 条最短路经的长度.你的程序需要读入农场的地图, 一些从 Xi
到 Yi 的路径和它们的长度(Xi,Yi,Di).
所有(Xi,Yi,Di) 满足( 1<=Yi<Xi; Yi<Xi<=N, 1<=Di<=1,000,000 ).
【输入】
第 1 行: 3 个数: N,M,K
第 2..M+1 行: 第 i+1 行包含 3 个数 Xi,Yi,Di, 表示一条下坡的路.
【输出】
第 1..K 行: 第 i 行包含第 i 最短路径的长度,或−1 如果这样的路径不存在.如果多条路径
有同样的长度,请注意将这些长度逐一列出.
【输入输出样例】
Input
5
5
5
5
5
4
3
3
2
8
4
3
2
1
3
1
2
1
7
1
1
1
1
4
1
1
1
Output
1
2
2
3
6
7
-1
【样例解释】
路径分别为(5−1),(5−3−1),(5−2−1),(5−3−2−1),(5−4−3−1),(5−4−3−2−1)
k短路，A*搜所，构造反图，处理处终点到每个点的最短距离，每次开启队列里dist+dis[u]最小的来扩展，一旦扩展到终点，就意味着找到了一条最短路，当第K次扩展到的时候就是第K短路。。。
1 #define ll long long 2 #include<algorithm> 3 #include<iostream> 4 #include<iomanip> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cstdio> 8 #include<queue> 9 #include<ctime> 10 #include<cmath> 11 #include<stack> 12 #include<map> 13 #include<set> 14 using namespace std; 15 const int N=1010,M=10010; 16 struct E{ 17 int to,net,w; 18 }e[M],e2[M]; 19 int n,m,k,num_e,num; 20 int head[N],h[N]; 21 void add(int x,int y,int w) { 22 e[++num_e].to=y;e[num_e].net=head[x];e[num_e].w=w;head[x]=num_e; 23 } 24 void add2(int x,int y,int w) { 25 e2[++num].to=y;e2[num].w=w;e2[num].net=h[x];h[x]=num; 26 } 27 int dis[N],cnt[N]; 28 bool inq[N]; 29 void spfa(int s,int t) { 30 queue<int> q; 31 q.push(s); 32 inq[s]=1; 33 memset(dis,0x3f,sizeof(dis)); 34 dis[s]=0; 35 while(!q.empty()) { 36 int u=q.front();q.pop(); 37 inq[u]=0;//不加会萎 38 for(int i=h[u];i;i=e2[i].net) { 39 int to=e2[i].to; 40 if(dis[to]>dis[u]+e2[i].w) { 41 dis[to]=dis[u]+e2[i].w; 42 if(!inq[to]) q.push(to),inq[to]=1; 43 } 44 } 45 } 46 } 47 struct Node{ 48 int id,dist; 49 bool operator<(const Node & b)const{ 50 return dist + dis[id] > b.dist +dis[b.id]; 51 } 52 };//Yinpengzhe200104234532 53 void a_star(int s,int t) { 54 priority_queue<Node> q; 55 Node tmp={s,0},tt; 56 q.push(tmp); 57 while(!q.empty()) { 58 tmp=q.top();q.pop(); 59 cnt[tmp.id]++; 60 if(tmp.id==t) { 61 printf("%d ",tmp.dist); 62 if(cnt[tmp.id]==k) return; 63 } 64 if(cnt[tmp.id]>k) continue; 65 for(int i=head[tmp.id];i;i=e[i].net) { 66 int to=e[i].to; 67 tt=(Node){to,tmp.dist+e[i].w}; 68 q.push(tt); 69 } 70 } 71 } 72 int main() { 73 freopen("cowjog.in","r",stdin); 74 freopen("cowjog.out","w",stdout); 75 cin>>n>>m>>k;int i; 76 for(i=1;i<=m;i++) { 77 int x,y,w; 78 scanf("%d%d%d",&x,&y,&w); 79 add(x,y,w);add2(y,x,w); 80 } 81 spfa(1,n); 82 a_star(n,1); 83 while(cnt[1]<k) puts("-1"),cnt[1]++; 84 return 0; 85 }
。。。。。。