当前位置: 代码迷 >> 综合 >> CCPC 2050 热身赛
  详细解决方案

CCPC 2050 热身赛

热度:8   发布时间:2023-12-12 17:29:31.0

A

赶火车

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4    Accepted Submission(s): 4


 

Problem Description

小伙伴们愉快地结束了暑假wannafly训练营的生活,决定返回学校,早上小伙伴们要赶到高铁站,高铁将在y分钟后停止检票,但他们发现了一件尴尬的事情——他们不认路。

这个城市的道路是非常诡异的,在他们面前有n+m条路,其中n条路是正确的,如果走正确的路,将会在ai分钟后走到高铁站,另外m条路是不正确的,如果走不正确的路,将会在bi分钟后回到起点。

小伙伴们只能随机选择一条路走,但他们记性很差,即使走过一条不正确的路,他们也可能会再次选择这条路。

小伙伴们是非常谨慎的人,他们想要计算到达高铁站所需时间的期望EX,如果EX≤y,那么就出发,否则就退票。

 

 

Input

第一行是一个整数T,表示有T组数据,接下来T组数据,每组数据包含三行:
n,m,y
a1,a2,...,an
b1,b2,...,bm
含义如题中所述
1≤T≤100,1≤n,m≤10,1≤ai,bi,y≤1000

 

 

Output

对于每组数据,如果要出发,那么就输出“Go”,否则输出“Wait”,不含引号。

 

 

Sample Input

 
 

2 4 7 2 1 1 1 1 1 1 1 1 1 1 1 7 4 2 1 1 1 1 1 1 1 1 1 1 1

 

 

Sample Output

 
 

Wait Go

//
//#include <bits/stdc++.h>
//#include <time.h>
//#define fi first
//#define se second
//#define endll "\n"
//#define MS0(X) memset((X), 0, sizeof((X)))
//#define MS1(X) memset((X), -1, sizeof((X)))
//#define LEN(X) strlen(X)
//#define INF 0x3f3f3f3f3f3f3f3f
//#define inf 0x3f3f3f3f
/vector(len,val);
//using namespace std;
//
//typedef long long ll;
//typedef double db;
//int xx[4] = {1,-1,0,0};
//int yy[4] = {0,0,1,-1};
//const double eps = 1e-9;
//typedef pair<int,int>  P;
//const int maxn = 2e6 + 5000;
//const ll mod = 1e9 + 7;
//inline int sign(db a) { return a < -eps ? -1 : a > eps;}
//inline int cmp(db a,db b){ return sign(a - b);}
//void debug(int x){  cout << x << endl; }
//ll mul(ll a,ll b,ll c) { ll res = 1; while(b) {  if(b & 1) res *= a,res %= c;  a *= a,a %= c,b >>= 1;  }  return res;}
//ll phi(ll x) {  ll res = x;  for(ll i = 2; i * i <= x; i++) { if(x % i == 0) res = res / i * (i - 1);   while(x % i == 0) x /= i;   }  if(x > 1) res = res / x  * (x - 1);    return res;}
//
//int fa[maxn];
//int Find(int x) {   if(x != fa[x]) return fa[x] = Find(fa[x]);  return fa[x];}
//ll c,n,k,m,y;
//ll a[maxn];
//ll s[maxn];
//int main() { int t;
//    ios::sync_with_stdio(false);
//    ll x,y;
//    cout << 1380.9 << endl;cin >> t;while(t--){cin >> n;cout << n * (n - 1) / 2 + n - 1 << endl;
//          n * (n + 3ll ) / 2ll}cerr << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
//    return 0;
//}
//
15 + 40 + 54 + 48 + 25
#include <bits/stdc++.h>
#include <time.h>
#define fi first
#define se second
#define endll "\n"
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
///vector(len,val);
using namespace std;typedef long long ll;
typedef double db;
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
const double eps = 1e-9;
typedef pair<int,int>  P;
const int maxn = 2e6 + 5000;
const ll mod = 1e9 + 7;
inline int sign(db a) { return a < -eps ? -1 : a > eps;}
inline int cmp(db a,db b){ return sign(a - b);}
void debug(int x){  cout << x << endl; }
ll mul(ll a,ll b,ll c) { ll res = 1; while(b) {  if(b & 1) res *= a,res %= c;  a *= a,a %= c,b >>= 1;  }  return res;}
ll phi(ll x) {  ll res = x;  for(ll i = 2; i * i <= x; i++) { if(x % i == 0) res = res / i * (i - 1);   while(x % i == 0) x /= i;   }  if(x > 1) res = res / x  * (x - 1);    return res;}int fa[maxn];
int Find(int x) {   if(x != fa[x]) return fa[x] = Find(fa[x]);  return fa[x];}
ll c,n,k,m,y;
ll a[maxn];
ll s[maxn];
int main() { int m,t;ios::sync_with_stdio(false);cin >> t;while(t--){cin >> n >> m >> y;y *= n;ll ans = 0;for(int i = 1;i <= n + m;i++){ll x;            cin >> x; ans += x;}if(ans <= y) cout << "Go" << endl;else cout << "Wait" << endl;}
//    cerr << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}//15 +

B

美丽度

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1    Accepted Submission(s): 1


 

Problem Description

街道上依次坐落着n个景点,每个景点都有一个美丽度a[i]。
定义[l,r]之间景点的美丽度为(r-l+1)*a[l]+(r-l)*a[l+1]+...+2*a[r-1]+1*a[r]
现在我们想要知道对于所有的子区间,景点的美丽度和为多少。

 

 

Input

第一行输入一个整数n(1<n<=1000000),
第二行输入n个整数。
0<=ai<=1e9

 

 

Output

输出所有区间的美丽度和(由于输出结果太大,答案取模1e9+7)。

 

 

Sample Input

3 1 2 3

5 1 2 3 4 5

 

 

Sample Output

 
 

27 182

 

很简单一个题,把两个样例写出来就可以看出贡献了

a_i的贡献为 a[i] * i * (n - i + 1) * (n - i + 2) / 2,注意取模

#include <bits/stdc++.h>
#include <time.h>
#define fi first
#define se second
#define endll "\n"
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
///vector(len,val);
using namespace std;typedef long long ll;
typedef double db;
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
const double eps = 1e-9;
typedef pair<int,int>  P;
const int maxn = 2e6 + 5000;
const ll mod = 1e9 + 7;
inline int sign(db a) { return a < -eps ? -1 : a > eps;}
inline int cmp(db a,db b){ return sign(a - b);}
void debug(int x){  cout << x << endl; }
ll mul(ll a,ll b,ll c) { ll res = 1; while(b) {  if(b & 1) res *= a,res %= c;  a *= a,a %= c,b >>= 1;  }  return res;}
ll phi(ll x) {  ll res = x;  for(ll i = 2; i * i <= x; i++) { if(x % i == 0) res = res / i * (i - 1);   while(x % i == 0) x /= i;   }  if(x > 1) res = res / x  * (x - 1);    return res;}int fa[maxn];
int Find(int x) {   if(x != fa[x]) return fa[x] = Find(fa[x]);  return fa[x];}
ll c,n,k,m,y;
ll a[maxn];
ll s[maxn];
int main() { int m,t;ios::sync_with_stdio(false);while(cin >> n){for(int i = 1;i <= n;i++) cin >> a[i];ll cnt = n,ans = 0;for(ll i = 1;i <= n;i++){ll x = (1ll + cnt) * cnt / 2ll; x %= mod;ans += (x * a[i]) % mod * i % mod;ans %= mod;cnt--;}cout << ans << endl;}
//    cerr << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;return 0;
}//15 + 40 + 54 + 48 + 25

C:没意义略

D:

定理证明

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1    Accepted Submission(s): 1


 

Problem Description

现在我们有n个定理,并且这n个定理是等价的,也就是说从任意一个定理出发,都可以推出其他所有的定理。

例如
定理1:有上界的实数集合必有上确界
定理2:有界实数列必有收敛子列
定理3:单调有界的实数列一定收敛

一共存在定理1→定理2、定理2→定理1、定理1→定理3、定理3→定理1、定理2→定理3、定理3→定理2这六种推导关系,但很显然有些推导是冗余的,例如,如果已经证明了定理1→定理2、定理2→定理3,那么定理1→定理3是显然成立的,证明定理1→定理3就是多余的。

请问我们最多可以按顺序写出多少个推导关系,使得其中任意一个推导关系和前面的结合起来不是多余的?

 

 

Input

第一行是一个整数T,表示有T组数据,接下来T组数据,每组数据包含一个整数n表示定理的个数。
1≤T≤100,1≤n≤1000

 

 

Output

对于每组数据,输出答案除以 10^9+7 的余数。

 

 

Sample Input

 
 

3 1 2 3

 

 

Sample Output

 
 

0 2 5

Hint

证明定理1→定理2、定理2→定理3,那么定理1→定理3是冗余的 证明定理1→定理2、定理1→定理3,那么定理2→定理3不是冗余的

手动写到5就可以发现规律了 ,n --, n * (n + 3) / 2,比较简单

代码略

  相关解决方案