A,B,J三题较为水,算是一眼题了
C. Pen Counts
题意:用1--n之间的数组成符合题意的三角形(每个数只能用一次),求三角形的个数。
经过统计,如果三条边的值完全不同,三角形个数+2,否则三角形个数+1,然后用过的三条边,就不能再用了。所以直接暴力找,中间弄点剪枝就能过了。
#include <cstdio> #include <iostream> #include <cmath> #include <cstring> using namespace std; int main() { int T,ca,n; scanf("%d",&T); while(T--) { scanf("%d%d",&ca,&n); int sum = 0; int len = n / 2; for(int i=len; i>=1; i--) { for(int j=i; j>=1; j--) { int k = n - i - j; if(k > j) break ; if(k + j > i) { if(i != j && j != k && i != k) sum += 2; else sum ++; } } } printf("%d %d ",ca,sum); } return 0; }
D. Maximum Random Walk
一道概率DP题,用dp[i][j][k]表示走了i步,当前走在j点,过程中已经走过的最靠右边的点为k的概率..........相当暴力,二维的做法表示不懂
#include <iostream> #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <vector> #include <set> #include <queue> #include <stack> #include <climits>//形如INT_MAX一类的 #define MAX 100005 #define INF 0x7FFFFFFF #define REP(i,s,t) for(int i=(s);i<=(t);++i) #define mem(a,b) memset(a,b,sizeof(a)) #define mp(a,b) make_pair(a,b) #define L(x) x<<1 #define R(x) x<<1|1 # define eps 1e-5 //#pragma comment(linker, "/STACK:36777216") ///传说中的外挂 using namespace std; double ll,rr,stop; double dp[2][2111][2111]; int n,ca; void solve() { memset(dp,0,sizeof(dp)); dp[0][1000][1000] = 1; int cur = 0; for(int i=1; i<=n; i++) { for(int j=1000-i; j<=1000+i; j++) { int k = max(j,1000); for(; k<=i+1000; k++) { if(k > j) dp[1-cur][j][k] = dp[cur][j][k] * stop + dp[cur][j-1][k] * rr + dp[cur][j+1][k] * ll; else dp[1-cur][j][k] = dp[cur][j][k] * stop + (dp[cur][j-1][k] + dp[cur][j-1][j-1])* rr; } } cur = 1 - cur; } double sum = 0; for(int j=1000-n; j<=1000+n; j++) { int k = max(j,1000); for(; k<=1000+n; k++) { sum += dp[cur][j][k] * (k - 1000); } } printf("%d %.4f ",ca,sum); } int main() { int T; cin >> T; while(T--) { scanf("%d%d",&ca,&n); scanf("%lf%lf",&ll,&rr); stop = 1 - ll - rr; solve(); } return 0; }
F. The King's Ups and Downs
题意:给定了1---n的数字,现在要把他们排列:高低高低的排列,或者低高低高的排列...求出所有的排列数
表示数学能力太差了,只能写暴力的状态压缩DP..........dp[i][j][k]表示排到第i个位置,状态为j,第i-1个位置高于或者低于第i个位置时,总的排列数。状压完打表即可。
#include <iostream> #include <algorithm> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <vector> #include <set> #include <queue> #include <stack> #include <climits>//形如INT_MAX一类的 #define MAX 100005 #define INF 0x7FFFFFFF #define REP(i,s,t) for(int i=(s);i<=(t);++i) #define ll long long #define mem(a,b) memset(a,b,sizeof(a)) #define mp(a,b) make_pair(a,b) #define L(x) x<<1 #define R(x) x<<1|1 # define eps 1e-5 //#pragma comment(linker, "/STACK:36777216") ///传说中的外挂 using namespace std; int n; //long long dp[22][1<< 20][2]; // //long long solve() { // memset(dp,0,sizeof(dp)); // for(int i=1; i<=n; i++) { // dp[i][1<<(i-1)][0] = 1; // dp[i][1<<(i-1)][1] = 1; // } // int total = 1 << n; // for(int j=1; j<total; j++) { // for(int i=1; i<=n; i++) { // for(int k=1; k<i; k++) { // if((j & (1<<(i-1))) && (j & (1 << (k-1)))) { // dp[i][j][0] += dp[k][j ^ (1 << (i-1))][1]; // } // } // for(int k=i+1; k<=n; k++) { // if((j & (1 << (i-1))) && (j & (1 << (k-1)))) { // dp[i][j][1] += dp[k][j ^ (1 << (i-1))][0]; // } // } // } // } // long long sum = 0; // for(int i=1; i<=n; i++) { // sum += dp[i][(1<<n) - 1][0] + dp[i][(1<<n) - 1][1]; // } // return sum; //} long long table[] = {0,1,2,4,10,32,122,544,2770,15872,101042,707584, 5405530,44736512,398721962,3807514624LL,38783024290LL, 419730685952LL,4809759350882LL,58177770225664LL, 740742376475050LL}; int main() { int T,ca; cin >> T; while(T--) { scanf("%d%d",&ca,&n); printf("%d %lld ",ca,table[n]); } return 0; }