锐客网

  1. 首页 > it技术 > >

CSU|CSU 1976: 搬运工小明 1977: Bit-reversal Permutation 1978: LXX的图论题 1979: 古怪的行列式 1980: 不堪重负的树

【CSU|CSU 1976: 搬运工小明 1977: Bit-reversal Permutation 1978: LXX的图论题 1979: 古怪的行列式 1980: 不堪重负的树】1976: 搬运工小明

#include #include #include #include using namespace std; long long a[100010]; int main() { int T; cin>>T; while(T--) { int N,M; cin>>N>>M; memset(a,0,sizeof(a)); long long maxm=0; for(int i=1; i<=M; i++) { cin>>a[i]; maxm=a[i]>maxm?a[i]:maxm; } if(N>=M) { cout<maxm) { cnt++; i--; sum=0; } }if(cnt<=N) { cout<

1977: Bit-reversal Permutation
#include #include #include #include #include using namespace std; typedef long long LL; const int MAXN=2e5+10; int a[MAXN]; int main() { int T; scanf("%d",&T); while(T--) { memset(a,0,sizeof(a)); int n; scanf("%d",&n); for(int i=0; i>1; //cout<<"sum: "
1978: LXX的图论题
#include #include #include #include using namespace std; int N,M; double nmap[505][505]; void init() { for(int i=1; i>N>>M) { init(); bool suc=false; for(int i=0; i>u>>v>>w; nmap[u][v]=min(nmap[u][v],w); //都是有向边 } for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) for(int k=1; k<=N; k++) { if(nmap[j][k]>nmap[j][i]*nmap[i][k]) nmap[j][k]=nmap[j][i]*nmap[i][k]; } for(int i=1; i<=N; i++)//检查有没有环满足条件 if(nmap[i][i]<1) { suc=true; break; } if(suc) cout<<"YES"<

1979: 古怪的行列式
#include #include #include #include typedef long long ll; using namespace std; const int maxn = 10; int T, n; ll myints[] = {0,1,2,3,4,5,6,7}, sample[maxn][maxn]; ll checkSgn(){ // 计算逆序数。 int cnt = 0; for(int i = 0; i < n-1; i++) for(int j = i+1; j < n; j++) if(myints[j] < myints[i]) cnt++; if(cnt & 1) return -1; return 1; }int main(){ #ifdef TEST freopen("test.txt", "r", stdin); #endif // TESTcin >> T; while(T--){ cin >> n; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin >> sample[i][j]; ll res = 0; do{ ll temp = 1; for(int i = 0; i < n; i++){ temp *= sample[i][myints[i]]; if(i >= 2) if(sample[i][myints[i]] == 82 && sample[i-1][myints[i-1]] == 83 && sample[i-2][myints[i-2]] == 83){ temp /= (82*83*83); } } temp *= checkSgn(); // 将一次排列得出的结果乘上1或-1. res += temp; }while(next_permutation(myints, myints+n)); cout << res << endl; }return 0; }

1980: 不堪重负的树
#include #include #include #include using namespace std; typedef long long LL; const int maxn=200+5; const LL INF=1ll<<50; LL sum[maxn],dp[maxn][maxn],a[maxn],c[maxn]; int n,b[maxn]; int main() { int T; scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=1; i<=n; ++i)scanf("%lld",a+i); for(int i=1; i<=n; ++i)scanf("%d",b+i); for(int i=1; i<=n; ++i)c[i]=a[b[i]]; for(int i=1; i<=n; ++i)sum[i]=sum[i-1]+c[i]; for(int i=1; i<=n; ++i) for(int j=i+1; j<=n; ++j) dp[i][j]=INF; for(int i=1; i<=n; ++i)dp[i][i]=c[i]; for(int j=2; j<=n; ++j) { for(int i=j-1; i>0; --i) { dp[i][j]=min(dp[i][j-1],dp[i+1][j])+sum[j]-sum[i-1]; for(int k=i+1; k<=j-1; ++k) { dp[i][j]=min(dp[i][j],dp[i][k-1]+sum[j]-sum[i-1]+dp[k+1][j]); } } } printf("%lld\n",dp[1][n]); } return 0; }



    推荐阅读


    上一篇：日记之随记|日记之随记 59

    下一篇：51822配对