August 19, 2015
1001
#include <iostream>
#include <cstring>
using namespace std;
#define DO(n) for ( int ____n = n; ____n-->0; )
#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define DWN(i, b, a) for (int i=b-1;i>=a;--i)
#define REP_1(i, n) for (int i=1;i<=n;++i)
#define FOR_1(i, a, b) for (int i=a;i<=b;++i)
#define DWN_1(i, b, a) for (int i=b;i>=a;--i)
#define RST(A) memset(A, 0, sizeof(A))
typedef long long LL;
const int MOD = int(1e9) + 7;
struct Int{
int val;
operator int() const{return val;}
Int(int t){
val = t;
}
Int& operator -=(const int& rhs){
val -= rhs; if (val < 0) val += MOD;
return *this;
}
Int& operator +=(const int& rhs){
val += rhs; if (val >= MOD) val -= MOD;
return *this;
}
Int operator *(const int& rhs) const{
LL z = (LL) val * rhs % MOD;
return z;
}
};
const int N = int(1e2) + 9;
int a[N]; char op[N];
int Fact[N], Binom[N][N], dp[N][N];
int n;
int w(int l, int r){
return Fact[r-l];
}
int c(int l, int k, int r){
return Binom[r-l-1][k-l];
}
Int f(int l, int r){
int &z = dp[l][r]; if (z == -1){
Int zz = 0; FOR(k, l, r) if (op[k] == '*'){
zz += (Int) f(l, k) * f(k+1, r) * c(l, k, r);
}
else if (op[k] == '+'){
zz += (Int) f(l, k) * w(k+1, r) * c(l, k, r);
zz += (Int) w(l, k) * f(k+1, r) * c(l, k, r);
}
else{
zz += (Int) f(l, k) * w(k+1, r) * c(l, k, r);
zz -= (Int) w(l, k) * f(k+1, r) * c(l, k, r);
}
z = zz % MOD;
if (z < 0) z += MOD;
}
return z;
}
//(3+5+7) + (2+4+7)
int main(){
#ifndef ONLINE_JUDGE
freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
//freopen("/users/xiaodao/desktop/Exercise/out.txt", "w", stdout);
#endif
Fact[0] = 1; FOR(i, 1, N) Fact[i] = Int(Fact[i-1]) * i;
REP(i, N){
Binom[i][0] = 1;
REP_1(j, i) Binom[i][j] = (Binom[i-1][j-1] + Binom[i-1][j]) % MOD;
}
while (~scanf("%d", &n)){
REP(i, n) scanf("%d", &a[i]); scanf("%s", op); memset(dp, -1, sizeof(dp));
REP(i, n) dp[i][i] = a[i];
printf("%d\n", f(0, n-1));
}
}
1004
#include <iostream>
#include <cstring>
using namespace std;
#define DO(n) for ( int ____n = n; ____n-->0; )
#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define DWN(i, a, b) for (int i=a-1;i>=b;--i)
#define RST(A) memset(A, 0, sizeof(A))
typedef long long LL;
const int MOD = int(1e9) + 7;
int pow(int a, int b){
int z = 1;
while (b){
if (b&1) z = (LL)z * a % MOD;
a = (LL)a * a % MOD; b >>= 1;
}
return z;
}
const int N = int(1e2) + 9;
int Fact[N], P[N][N], I[N], II[N]; bool vis[N];
int n, m;
int solve(){
bool bad = false; int d = 0; REP(i, m){
scanf("%d", &P[i][0]);
if (P[i][0] == -1) ++d;
else{
RST(vis); vis[P[i][0]] = true;
FOR(j, 1, n){
scanf("%d", &P[i][j]);
if (vis[P[i][j]]) bad = true;
vis[P[i][j]] = true;
}
}
}
if (bad) return 0;
if (d){
return pow(Fact[n], d-1);
}
else{
REP(i, n) I[i] = i; DWN(i, m, 0){
REP(j, n) II[j] = I[j];
REP(j, n) I[j] = P[i][II[j]] - 1;
}
REP(i, n) if (I[i] != i) return 0;
return 1;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
//freopen("/users/xiaodao/desktop/Exercise/out.txt", "w", stdout);
#endif
Fact[0] = 1; FOR(i, 1, N) Fact[i] = (LL) Fact[i-1] * i % MOD;
while (cin >> n >> m){
cout << solve() << endl;
}
}
1005
#include <iostream>
#include <cstring>
using namespace std;
#define DO(n) for ( int ____n = n; ____n-->0; )
#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define DWN(i, b, a) for (int i=b-1;i>=a;--i)
#define REP_1(i, n) for (int i=1;i<=n;++i)
#define FOR_1(i, a, b) for (int i=a;i<=b;++i)
#define DWN_1(i, b, a) for (int i=b;i>=a;--i)
#define RST(A) memset(A, 0, sizeof(A))
typedef long long LL;
const int N = int(1e5) + 9;
int A[N], L[N], R[N], n, d1, d2;
LL solve(){
LL z = 0;
REP(i, n) scanf("%d", &A[i]);
REP(i, n-1){
if (A[i+1] - A[i] == d1){
L[i+1] = L[i] + 1;
}
else{
L[i+1] = 0;
}
}
R[n-1] = 0;
DWN(i, n-1, 0){
if (A[i+1] - A[i] == d2){
R[i] = R[i+1] + 1;
}
else{
R[i] = 0;
}
}
if (d1 == d2){
/*REP(i, n){
z += (LL)(R[i]+1)*(R[i]+2) / 2;
i += R[i];
}
return z;*/
REP(i, n) L[i] = 0;
}
REP(i, n){
z += (LL) (L[i]+1)*(R[i]+1);
}
return z;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
//freopen("/users/xiaodao/desktop/Exercise/out.txt", "w", stdout);
#endif
while (cin >> n >> d1 >> d2){
cout << solve() << endl;
}
}
1007
#include <iostream>
using namespace std;
#define DO(n) for ( int ____n = n; ____n-->0; )
#define REP(i, n) for (int i=0;i<n;++i)
const int N = int(1e2) + 9;
int A[N][N];
int n, m;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, 1};
const char op[] = {'D', 'R', 'U', 'R'};
const int SZ = 4;
void snake(int x, int y, int tx, int ty){
int p = 0; bool flag = true; DO(2*(m-1) - 1){
if (x+dx[p] == tx && y+dy[p] == ty){
flag = false; ++y;
putchar('R');
}
x += dx[p]; y += dy[p]; putchar(op[p]);
++p; if (p == SZ) p = 0;
}
if (flag) putchar('R');
}
int main() {
#ifndef ONLINE_JUDGE
freopen("/users/xiaodao/desktop/Exercise/in.txt", "r", stdin);
//freopen("/users/xiaodao/desktop/Exercise/out.txt", "w", stdout);
#endif
while (cin >> n >> m){
int z = 0; REP(i, n) REP(j, m){
scanf("%d", &A[i][j]);
z += A[i][j];
}
if (n&1){
cout << z << endl;
REP(i, n){
DO(m-1) putchar( (i&1) ? 'L' : 'R');
if (i != n-1) putchar('D');
}
}
else if (m&1){
cout << z << endl;
REP(i, m){
DO(n-1) putchar( (i&1) ? 'U' : 'D');
if (i != m-1) putchar('R');
}
}
else{
int x = 0, y = 1;
REP(i, n) REP(j, m) if ((i+j)&1){
if (A[i][j] < A[x][y]){
x = i, y = j;
}
}
z -= A[x][y];
cout << z << endl;
bool flag = true;
REP(i, n/2){
if (i) putchar('D');
if (flag){
if (x/2 == i){
snake(i*2, 0, x, y);
flag = false;
continue;
}
DO(m-1) putchar('R'); putchar('D');
DO(m-1) putchar('L');
}
else{
DO(m-1) putchar('L'); putchar('D');
DO(m-1) putchar('R');
}
}
}
puts("");
}
}
4 2
1 1
1 1
1 1
1 1
2 4
1 1 1 1
1 1 1 1
Posted by
xiaodao
Category: Multi-University Training
