第四届“图灵杯”NEUQ-ACM程序设计竞赛总结【8/10】

101 阅读 0 评论 67 点赞

我是靠谱客的博主缓慢薯片，这篇文章主要介绍第四届“图灵杯”NEUQ-ACM程序设计竞赛总结【8/10】，现在分享给大家，希望可以做个参考。

训练结果：金（Rank.13）.

Ac题数：8.

tot tiime：1318.

流水账：

开场日常爆炸，最水最简单的题还Wa了一发= =.

30分钟过了3个题，手速还是蛮快的。

然后就是一段长达接近两个半小时的不出题阶段。

AE各Wa了一发，F，TLE了一发。

全程交替，没过题。

直到队长彻底的放弃了E题，我接手切掉（老OJ不开O2加速，只要用Map就TLE也是带来两发罚时很不开心），然后过掉A（队长推出正确式子）.再之后讨论了一下F是不是单组输入问题，改掉之后果然过了。然后Java写了一发大数过掉了C.

三十分钟就连续过了4个题= =

日常，日常。

最后剩下一个多小时队长写掉了字典树，Splay不会H就放着了。

最后八题。

题解：

A:一道推公式的组合数学，不难。我是萌萌哒A题题解

B:全场签到水题

C:Java大数随便谢谢就行。（妈蛋我处女Java题= =）

D:分形Dfs.（贴上队长代码）

复制代码

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
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
typedef long long int LL;
using namespace std;
const int N
= 1e6+7;
const int MOD = 1e9+7;
/********************************************/
char a[3333][3333];
int mypow(int a,int b){
int res=1ll;
while(b){
if(b&1) res=res*a;
a=a*a,b>>=1;
}
return res;
}
void dayin(int cur,int x,int y){
if(cur==1){
a[x][y]='/';
a[x+1][y-1]='/';
a[x][y+1]='\';
a[x+1][y+2]='\';
a[x+1][y+1]='_';
a[x+1][y]='_';
return ;
}
int h = mypow(2,cur);
//
int l = mypow(2,cur+1);
dayin(cur-1,x,y);
dayin(cur-1,x+h/2,y-h/2);
dayin(cur-1,x+h/2,y+h/2);
}
int n;
int main(){
int flag = 0;
while(~scanf("%d",&n)&&n){
if(flag) puts("");flag=1;
memset(a,' ',sizeof(a));
int h=mypow(2,n);
int l=mypow(2,n+1);
//
printf("%d %dn",h,l);
dayin(n,1,l/2);
for(int i=1;i<=h;i++){
for(int j=l;j;j--){
if(a[i][j]!=' '){
a[i][j+1]='';
break;
}
}
}
for(int i=1;i<=h;i++)
printf("%sn",a[i]+1);
}
return 0;
}

E:一道线段树，维护左右要删除的数的个数就行。我是萌萌哒E题题解

F:矩阵快速幂裸题（贴上队长代码），但是必须单组输入，这里被卡了好多发罚时。。。。

另外注意，K是1e10不是1e9....

复制代码

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
typedef long long int LL;
using namespace std;
#define abs(x) (((x)>0)?(x):-(x))
const int N = 3000+10;
const int MOD
= 1e9+7;
/*******************************/
const int M = 101;
LL n,k;
struct Matrix {
LL m[M][M];
void clear0(){
for(int i=0;i<M;i++)
for(int j=0;j<M;j++)
m[i][j]=0;
}
void clear1(){
for(int i=0;i<M;i++)
for(int j=0;j<M;j++)
m[i][j]=(i==j);
}
void display(){
for(int i=0;i<M;i++){
for(int j=0;j<M;j++)
printf("%lld ",m[i][j]);
puts("");
}
puts("------");
}
};
Matrix operator * (Matrix &a, Matrix &b){
Matrix c;c.clear0();
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;
return c;
}
Matrix operator ^(Matrix &a,LL b){
Matrix c;c.clear1();
if(b<=0) return c;
while(b){
if(b&1) c=c*a;
b>>=1,a=a*a;
}
return c;
}
LL f[111],aa[111];
Matrix a,b;
void solve(){
a.clear0();b.clear0();
for(int i=0;i<n;i++) a.m[0][i]=f[i+1];
for(int i=0;i<n;i++){
b.m[i+1][i]=1;
b.m[i][n-1]=aa[n-i];
}
b=b^(k-n);
a=a*b;
printf("%lldn",a.m[0][n-1]);
}
int main(){
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++) scanf("%lld",&f[i]);
for(int i=1;i<=n;i++) scanf("%lld",&aa[i]);
solve();
return 0;
}

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
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
typedef long long int LL;
using namespace std;
#define abs(x) (((x)>0)?(x):-(x))
const int N = 3000+10;
const int MOD
= 1e9+7;
/*******************************/
const int M = 101;
LL n,k;
struct Matrix {
LL m[M][M];
void clear0(){
for(int i=0;i<M;i++)
for(int j=0;j<M;j++)
m[i][j]=0;
}
void clear1(){
for(int i=0;i<M;i++)
for(int j=0;j<M;j++)
m[i][j]=(i==j);
}
void display(){
for(int i=0;i<M;i++){
for(int j=0;j<M;j++)
printf("%lld ",m[i][j]);
puts("");
}
puts("------");
}
};
Matrix operator * (Matrix &a, Matrix &b){
Matrix c;c.clear0();
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;
return c;
}
Matrix operator ^(Matrix &a,LL b){
Matrix c;c.clear1();
if(b<=0) return c;
while(b){
if(b&1) c=c*a;
b>>=1,a=a*a;
}
return c;
}
LL f[111],aa[111];
Matrix a,b;
void solve(){
a.clear0();b.clear0();
for(int i=0;i<n;i++) a.m[0][i]=f[i+1];
for(int i=0;i<n;i++){
b.m[i+1][i]=1;
b.m[i][n-1]=aa[n-i];
}
b=b^(k-n);
a=a*b;
printf("%lldn",a.m[0][n-1]);
}
int main(){
scanf("%lld%lld",&n,&k);
for(int i=1;i<=n;i++) scanf("%lld",&f[i]);
for(int i=1;i<=n;i++) scanf("%lld",&aa[i]);
solve();
return 0;
}

G:贴上来官方题解：

找规律。
51#1最优解1+（111-11）／（1+1）
51#2最优解2+2/2+2*（2*2）！
51#3最优解3!*3+33
51#4最优解4!*(√4+√√√(√4^(-4!)))
51#5最优解5/5+55-5
51#6最优解(6!-6*6)/(6+6)-6
51#7最优解7*7+(7+7)/7
51#8最优解√√(8+8)+√(√(8-8/8)^8)
51#9最优解(√9)!*9-√9
51的9个最优解是864456563

H:听队长说是Splay什么的，反正弊队不会= =，再贴一发官方题解：

splay树。
每次颠倒把要操作的区间转成一棵子树，然后更新。每次把p转到根，然后翻转左子树，删除根。
本题的话每个结点序号就是最开始的位置。sp树中第i个结点的序号就是第i个数的初始位置。所以对每个数排序，记录初始位置，就可以在树中直接找到要操作的结点。

I:全场签到水题= =

J:一发字典树，先给各个单词排个序，然后统计个数就行了（贴一发队长代码）。

复制代码

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string a[30003];
char
b[30003][20];
int trie[25000*20][27],val[25000*20];
int cnt,tot;
vector<string>vc[30003];
void inserttrie(char *s,int id){
int now = 0;
for(int i=0;s[i];i++){
if(0==trie[now][s[i]-'a']) trie[now][s[i]-'a']=++cnt;
now = trie[now][s[i]-'a'];
}
if(0==val[now]) val[now] = ++tot;
vc[val[now]].push_back(a[id]);
}
bool cmp(vector<string> a, vector<string> b){
if(a.size()==b.size()){
return a[0]<b[0];
}
return a.size()>b.size();
}
int main(){
int l = 1;
cnt=tot=0;
while(cin>>a[l]){
int la = a[l].size();
for(int i=0;i<la;i++)
b[l][i]=a[l][i]; b[l][la]='';
sort(b[l],b[l]+la);
l++;
}
l--;
for(int i=1;i<=l;i++)
inserttrie(b[i],i);
for(int i=1;i<=tot;i++)
sort(vc[i].begin(),vc[i].end());
sort(vc+1,vc+tot+1,cmp);
for(int i=1;i<=5;i++){
int gz=vc[i].size();
if(gz==0) break;
cout<<"Group of size "<<gz<<":";
cout<<" "<<vc[i][0];
for(int j=1;j<gz;j++)
if(vc[i][j]!=vc[i][j-1])
cout<<" "<<vc[i][j];
cout<<" ."<<endl;
}
return 0;
}

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
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string a[30003];
char
b[30003][20];
int trie[25000*20][27],val[25000*20];
int cnt,tot;
vector<string>vc[30003];
void inserttrie(char *s,int id){
int now = 0;
for(int i=0;s[i];i++){
if(0==trie[now][s[i]-'a']) trie[now][s[i]-'a']=++cnt;
now = trie[now][s[i]-'a'];
}
if(0==val[now]) val[now] = ++tot;
vc[val[now]].push_back(a[id]);
}
bool cmp(vector<string> a, vector<string> b){
if(a.size()==b.size()){
return a[0]<b[0];
}
return a.size()>b.size();
}
int main(){
int l = 1;
cnt=tot=0;
while(cin>>a[l]){
int la = a[l].size();
for(int i=0;i<la;i++)
b[l][i]=a[l][i]; b[l][la]='';
sort(b[l],b[l]+la);
l++;
}
l--;
for(int i=1;i<=l;i++)
inserttrie(b[i],i);
for(int i=1;i<=tot;i++)
sort(vc[i].begin(),vc[i].end());
sort(vc+1,vc+tot+1,cmp);
for(int i=1;i<=5;i++){
int gz=vc[i].size();
if(gz==0) break;
cout<<"Group of size "<<gz<<":";
cout<<" "<<vc[i][0];
for(int j=1;j<gz;j++)
if(vc[i][j]!=vc[i][j-1])
cout<<" "<<vc[i][j];
cout<<" ."<<endl;
}
return 0;
}