2018东北农业大学春季校赛 B 题目要求 n矩阵，按照顺序填入1到n n的数，例如n=5，该矩阵如下
输入描述
输出描述
输入
输出
参考AC代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
using namespace std;
int t,n;
int main
// freopen("input.txt" ,"r" ,stdin);
cin>>t;
while (t--){
cin>>n;
int st=(n+1)/2,ed=0;
LL ans=0;
ans+=(LL)st;
for (int i=2;i<=n/2+1;i++){
st=st+(n-(2*i-3))+(2*i-4);
ed=st+(2*i-2);
ans+=(LL)(st+ed)*(2*i-1)/2;
// cout<<st<<" " <<ed<<endl;
}
st=n*n-n/2;
ans+=(LL)st;
for (int i=2;i<=n/2;i++){
st=st-(n-(2*i-3))-(2*i-4);
ed=st-(2*i-2);
ans+=(LL)(st+ed)*(2*i-1)/2;
// cout<<st<<" " <<ed<<endl;
}
cout<<ans<<endl;
}
return 0;
}
思路 手动算出每行的st和ed 然后用等差数列求和公式 累加即可
D 题目要求
输入描述
输出描述
输入
输出
参考AC代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
using namespace std;
int t,n,m;
int sx,sy,ex,ey;
int flag;
char mp[maxn][maxn];
int vis[maxn][maxn];
int dirx[4]={0,0,1,-1};
int diry[4]={1,-1,0,0};
bool check(int x,int y){
if (x<1 || x>n || y<1 || y>m || vis[x][y] || mp[x][y]=='x' ) return true ;
return false ;
}
void dfs(int x,int y){
if (x==ex && y==ey){
flag=1;
return ;
}
for (int i=0;i<4;i++){
int nextx=x+dirx[i];
int nexty=y+diry[i];
if (check(nextx,nexty)) continue ;
vis[nextx][nexty]=1;
dfs(nextx,nexty);
}
}
int main
// freopen("input.txt" ,"r" ,stdin);
cin>>t;
while (t--){
cin>>n>>m;
for (int i=1;i<=n;i++){
scanf("%s" ,mp[i]+1);
}
flag=0;
memset(vis,0,sizeof vis);
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
if (mp[i][j]=='s' ) sx=i,sy=j;
if (mp[i][j]=='t' ) ex=i,ey=j;
}
}
vis[sx][sy]=1;
dfs(sx,sy);
if (flag) cout<<"YES" <<endl;
else cout<<"NO" <<endl;
}
return 0;
}
思路 dfs裸搜 注意不需要回溯
E 题目要求
输入描述
输出描述
输入
输出
参考AC代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using namespace std;
int t,n;
int main
// freopen("input.txt" ,"r" ,stdin);
cin>>t;
while (t--){
cin>>n;
int num=0,tmp=5;
while (1){
if (n/tmp==0) break ;
num+=n/tmp;
tmp*=5;
}
cout<<num<<endl;
}
return 0;
}
思路 转跳链接
F 题目要求
连接的两个点必须在不同的两个集合
一个集合内部任意两个点之间不能相连
输入描述
输出描述
输入
输出
参考AC代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
using namespace std;
int t,n;
int main
// freopen("input.txt" ,"r" ,stdin);
cin>>t;
while (t--){
cin>>n;
if (n&1) cout<<(LL)(n/2)*(n/2+1)<<endl;
else cout<<(LL)(n/2)*(n/2)<<endl;
}
return 0;
}
思路 分成两部分集合 均分成就是:(偶数)偶数×偶数 (奇数)奇数×偶数
I 题目要求
输入描述
输出描述
输入
输出
参考AC代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
using namespace std;
const double eps = 1e-4;
int t,n,k;
double a[maxn];
double value[maxn],weight[maxn];
bool cmp(double a,double b){
return a>b;
}
bool check(double x){
memset(a,0,sizeof a);
for (int i=1;i<=n;i++) a[i]=value[i]-x*weight[i];
sort(a+1,a+1+n,cmp);
double ans=0;
for (int i=1;i<=k;i++) ans+=a[i];
return ans>=0;
}
int main
// freopen("input.txt" ,"r" ,stdin);
cin>>t;
while (t--){
cin>>n>>k;
for (int i=1;i<=n;i++) cin>>weight[i]>>value[i];
double l=0.0,r=100000000.0,ans=0.0;
while (l-r<=eps){
double mid=(l+r)/2.0;
if (check(mid)){
ans=mid;
l=mid+eps;
}
else r=mid-eps;
}
printf ("%.2lf\n" ,ans);
}
return 0;
}
思路 分数最优规划 二分
K 题目要求
输入描述
输出描述
输入
输出
参考AC代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
using namespace std;
int t,c;
int f[maxn];
LL a,b;
LL qpow(LL x,LL y,int mod){
LL re=1,base=x%mod;
while (y){
if (y&1) re=(re*base)%mod;
base=(base*base)%mod;
y>>=1;
}
return re;
}
int main
// freopen("input.txt" ,"r" ,stdin);
cin>>t;
while (t--){
cin>>a>>b>>c;
f[0]=0,f[1]=1;
int num=0;
for (int i=2;i<=1000100;i++){
f[i]=(f[i-1]+f[i-2])%c;
if (f[i-1]==0 && f[i]==1){
num=i-1;
break ;
}
}
int pos=qpow(a,b,num);
cout<<f[pos]<<endl;
}
return 0;
}
思路 找出循环节+快速幂
L 题目要求
输入描述
输出描述
输入
输出
参考AC代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
using namespace std;
const int Maxn = 500050;
struct Treap{
Treap* Ch[2];
int p,v,S;
};
int root = 0,n,q,x,a[Maxn];
void Update(Treap* &o){
siz = 1;
if (Lc != NULL)siz += Lc -> S;
if (Rc != NULL)siz += Rc -> S;
}
void Rotate(Treap* &o,int d){
Treap* P = o -> Ch[d^1];
o -> Ch[d^1] = P -> Ch[d];
P -> Ch[d] = o;
Update(o);Update(P);
o = P;
}
void Insert(Treap* &o,int x){
o = new Treap();
Lc = Rc = NULL;
pre = rand();val = x;
}
else {
int d = x < val;
Insert(o -> Ch[d],x);
if ( ( pre ) > o -> Ch[d] -> p)Rotate(o,d^1);
}
Update(o);
}
int Find(Treap* o,int x){
while (o != NULL){
if (val == x)return 1;
o = (x < val) ? Rc : Lc ;
}return 0;
}
void Delete(Treap* &o,int x){
if (val == x){
if (Lc == NULL)o = Rc;
else if (Rc == NULL)o = Lc;
else {
int T = (Lc -> p) < (Rc -> p);
Rotate(o,T);Delete(o -> Ch[T],x);
}
}
else Delete(o -> Ch[x < val],x);
if (o != NULL)Update(o);
}
int Kth_Min (Treap* o,int k){
if (o == NULL || k <= 0 || k > siz)return 0;
int S = (Rc == NULL) ? 0 : (Rc -> S);
if (k == S + 1)return val;
else if (k <= S)return Kth_Min (Rc,k);
else return Kth_Min (Lc,k - S - 1);
}
int Kth_Max(Treap* o,int k){
if (o == NULL || k <= 0 || k > siz)return 0;
int S = (Lc == NULL) ? 0 : (Lc -> S);
if (k == S + 1)return val;
else if (k <= S)return Kth_Max(Lc,k);
else return Kth_Max(Rc,k - S - 1);
}
void Print(Treap* o){
printf ("%d " ,siz);
if (Lc != NULL)Print(Lc);
if (Rc != NULL)Print(Rc);
}
char op[100];
int main
int t;
cin>>t;
while (t--){
scanf("%d%d" ,&n,&q);
Treap* Root = NULL;
for (int i=1;i<=n;i++){
scanf("%d" ,&a[i]);
Insert(Root,a[i]);
}
while (q--){
scanf("%s" ,op);
int tmp;
cin>>tmp;
if (op[0]=='i' ) Insert(Root,tmp);
else if (op[0]=='d' ) Delete(Root,tmp);
else if (op[0]=='q' ) printf ("%d\n" ,Kth_Max(Root,tmp));
}
}
return 0;
}
思路 动态区间第k大 带删除插入查询
M 题目要去
输入描述
输出描述
输入
输出
参考AC代码 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
using namespace std;
int t;
char s[50];
int main
// freopen("input.txt" ,"r" ,stdin);
cin>>t;
while (t--){
scanf("%s" ,s+1);
int len=strlen(s+1);
int ans=0;
for (int i=1;i<=len;i++){
if (s[i]=='7' ) ans++;
}
cout<<ans<<endl;
}
return 0;
}
思路 字符串模拟
