T1 方陣
題目
【題目描述】
小澳最近迷上了考古，他發現秦始皇的兵馬俑布局十分有特點，熱愛鉆研的小澳打算在電腦上還原這個偉大的布局，
他努力鉆研，發現秦始皇布置兵馬俑是有一定規律的，兵馬俑陣總共有n行m列，秦始皇在布置的時候每次會指定一行或一列，然后指定一個兵種，使得這一行或者這一列上全部放上這一個兵種，如果這一行上以前放過其它的兵種，那么他會拔掉以前的兵種改成現在他命令的兵種，
小澳從秦朝的文獻中找到了布置這個方陣的操作順序，他希望你能告訴他布局完成后整個兵馬俑陣是什么樣子的，
【輸入格式】
輸入檔案共q+1行，
輸入檔案第1行包括三個正整數n,m,q，分別表示兵馬俑陣的行數和列數以及秦始皇總的運算元，
接下來q行，每行三個正整數x,y,z，x表示操作種類，若x=1表示給第y行(y≤n)全部放上z這個兵種，若x=2，則表示給第y列(y≤m)全部放上z這個兵種，資料保證z≤231-1，
【輸出格式】
n行，每行m個整數，分別用空格隔開，表示最后方陣上每個位置放的兵種，如果某個位置沒有被操作過輸出0，
【輸入樣例】
3 3 3 1 1 3 2 2 1 1 2 2
【輸出樣例】
3 1 3 2 2 2 0 1 0
【資料規模】
對于前20%的資料，n×m≤25，
對于前30%的資料，q≤2000，
對于100%的資料，n,m≤1000，n×m≤105，q≤106，
決議
驚！原題長樂培訓Day4t1！
送分題，直接模擬即可，不過得從后往前來，不然會超時，
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; int read() { int num=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } struct rec{ int p,x,y; }s[1000010]; int n,m,q,map[1010][1010]; int main() { //freopen("matrix.in","r",stdin); //freopen("matrix.out","w",stdout); int t; n=read(),m=read(),q=read(); for(int i=1;i<=q;i++) s[i].p=read(),s[i].x=read(),s[i].y=read(); for(int i=q;i>=1;i--) { if(s[i].p==1) { for(int j=1;j<=m;j++) if(!map[s[i].x][j]) map[s[i].x][j]=s[i].y; } else { for(int j=1;j<=n;j++) if(!map[j][s[i].x]) map[j][s[i].x]=s[i].y; } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) cout<<map[i][j]<<" "; cout<<endl; } return 0; }View Code
T2 排名
題目
【題目描述】
小明班里一共N名同學，小明這次考試考的不錯，他知道他考了多少分，以及班級里的同學一共考了多少分，小明還知道這次考試滿分為100，問小明最高可以排第幾，最低可以排第幾，
（相同分數算并列的排名，比如總共4個人7,6,6,5，那么他們的排名分別就是1,2,2,4）
【輸入格式】
第一行包括三個整數N,A,S，分別表示班里同學的人數，小明的分數，以及班里同學的總分，
【輸出格式】
包括兩個用空格隔開的正整數，分別表示小明在最優情況下的排名，以及在最壞情況下的排名，
【輸入樣例】
5 90 450
【輸出樣例】
1 4
【資料規模】
對于40%的資料，1≤N≤10；
對于100%的資料，1≤N≤105，0≤A≤100，0≤S≤100N，
決議
貪心：
計算最高排名時，先將所有人分數定為a，如果總分不夠或總分剛好夠，則第1；如果夠，則逐漸增加滿分人數，直到總分不夠或剛好夠，則排名為滿分人數+1，
計算最低排名時，先將所有人分數定為a+1，如果總分不夠，則排名為當前分數為a+1的總人數+1；如果夠，則排名為n，
注意a=100分的情況(此時a+1=101，超出滿分)，特判一下直接輸出即可，
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; int read() { int num=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } int n,a,s,num; int high(int ans) { for(int i=2;i<=n;i++) { if(ans>=a) ans-=a; else return 1; } if(ans==0) return 1; for(int i=2;i<=n;i++) { if(ans>=100-a) ans-=100-a; else return i; if(ans==0) return i; } return n; } int low(int ans) { for(int i=1;i<n;i++) { if(ans>=a+1) ans-=a+1; else return i; } return n; } int main() { //freopen("rank.in","r",stdin); //freopen("rank.out","w",stdout); n=read(),a=read(),s=read(),s-=a; if(a==100) cout<<"1 1"; else cout<<high(s)<<" "<<low(s); return 0; }View Code
T3 最長不下降子序列
題目
【題目描述】
給你一個正整數N，請你統計出所有的長度恰好為n的01序列的最長不下降子序列之和，
【輸入格式】
第一行包括一個正整數N，
【輸出格式】
一行包括一個整數表示所統計的答案，由于答案可能會很大，所以我們把答案對109+7取模，
【輸入樣例】
3
【輸出樣例】
20
【資料規模】
對于30%的資料，n≤20；
對于100%的資料，n≤200，
決議
DP題，令f[i][j][k]表示長度為i，以0結尾的最長不下降子序列長度為j,以1結尾的最長不下降子序列長度為k的方案數，初值均為0，邊界f[1][1][0]=f[1][0][1]=1，
狀態轉移方程：考慮給第i+1位上填0或1，
- 若第i+1位上填0，則f[i+1][j+1][k]+=f[i][j][k]，第i+1位為0，只能由第i位為0時得到，
- 若第i+1位上填1，則f[i+1][j][max(j,k)+1]+=f[i][j][k]，第i+1位為1，無論第i位是0還是1，其以1結尾的最長不下降子序列長度必然增加，因為1是最大的，故k取max(j,k)+1，
最終答案為max(j,k)*f[n][j][k]之和，
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; const int mod=1000000007; int n; long long ans,f[210][210][210];//f[i][j][k]表示長度為i,以0結尾最長不降子序列長度為j,以1結尾為k int main() { //freopen("lis.in","r",stdin); //freopen("lis.out","w",stdout); f[1][1][0]=1,f[1][0][1]=1; cin>>n; for(int i=1;i<=n;i++) for(int j=0;j<=i;j++) for(int k=0;k<=i;k++) { f[i+1][j+1][k]=(f[i+1][j+1][k]+f[i][j][k])%mod; f[i+1][j][max(j,k)+1]=(f[i+1][j][max(j,k)+1]+f[i][j][k])%mod; } for(int j=0;j<=n;j++) for(int k=0;k<=n;k++) ans=(ans+(long long)max(j,k)*f[n][j][k])%mod; cout<<ans; return 0; }View Code
T4 奇襲
題目
【題目描述】
給出一張N×N的網格圖，一共有N支軍隊駐扎在一些網格中（不會有兩只軍隊駐扎在一起），
每有一個k×k(1≤k≤N)的子網格圖包含恰好k支軍隊，襲擊的難度就會增加1點，請你計算出襲擊的難度，
【輸入格式】
第一行，一個正整數N，表示網格圖的大小以及軍隊數量，
接下來N行，每行兩個整數Xi,Yi，表示第i支軍隊的坐標，
保證每一行和每一列都恰有一只軍隊，即每一個Xi和每一個Yi都是不一樣的，
【輸出格式】
一行，一個整數表示襲擊的難度，
【輸入樣例】
5 1 1 3 2 2 4 5 5 4 3
【輸出樣例】
10
【資料規模】
對于前10%的資料，N≤100；
對于前40%的資料，N≤5000；
對于100%的資料，N≤50000，
決議
以下來源于出題人的題解，
對于每一個坐標(x,y)，記b[x]=y，故所求為序列b滿足下列條件的區間[l,r]的數量：
Code
#include <algorithm> #include <iostream> #include <cstring> #include <string> #include <cstdio> #include <cmath> using namespace std; int read() { int num=0,w=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { num=(num<<1)+(num<<3)+ch-'0'; ch=getchar(); } return num*w; } const int N=50100,M=100100; int n,a[N],maxl[N],maxr[N],minl[N],minr[N],bz[M*2]; long long work(int l,int r) { if(l==r) return 1; int mid=(l+r)>>1; maxl[mid]=minl[mid]=a[mid],maxr[mid+1]=minr[mid+1]=a[mid+1]; for(int i=mid-1;i>=l;i--) maxl[i]=max(maxl[i+1],a[i]),minl[i]=min(minl[i+1],a[i]); for(int i=mid+2;i<=r;i++) maxr[i]=max(maxr[i-1],a[i]),minr[i]=min(minr[i-1],a[i]); long long t=0; for(int i=mid;i>=l;i--) { int p=i+maxl[i]-minl[i]; if(p<=mid||p>r) continue; if(minr[p]>minl[i]&&maxr[p]<maxl[i]) t++; } for(int i=mid+1;i<=r;i++) { int p=i-maxr[i]+minr[i]; if(p>mid||p<l) continue; if(minl[p]>minr[i]&&maxl[p]<maxr[i]) t++; } int z1=mid+1,z2=mid; for(int i=mid;i>=l;i--) { while(minr[z2+1]>minl[i]&&z2<r) z2++,bz[maxr[z2]-z2+M]++; while(maxl[i]>maxr[z1]) { bz[maxr[z1]-z1+M]--,z1++; if(z1>r) break; } if(z1>r) break; if(z1<=z2) t+=bz[minl[i]-i+M]; } for(int i=mid;i>=l;i--) bz[minl[i]-i+M]=0; for(int i=mid+1;i<=r;i++) bz[maxr[i]-i+M]=0; z1=mid,z2=mid+1; for(int i=mid+1;i<=r;i++) { while(minl[z2-1]>minr[i]&&z2>l) z2--,bz[maxl[z2]+z2+M]++; while(maxr[i]>maxl[z1]) { bz[maxl[z1]+z1+M]--,z1--; if(z1<l) break; } if(z1<l) break; if(z2<=z1) t+=bz[minr[i]+i+M]; } for(int i=mid+1;i<=r;i++) bz[minr[i]+i+M]=0; for(int i=mid;i>=l;i--) bz[maxl[i]+i+M]=0; return t+work(l,mid)+work(mid+1,r); } int main() { n=read(); for(int i=1;i<=n;i++) { int x=read(),y=read(); a[x]=y; } cout<<work(1,n); return 0; }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/100202.html
標籤：C++