NEUQ-ACM程序设计竞赛(团队赛)

自用笔记算法

NEUQ-ACM程序设计竞赛(团队赛)

A

题目描述

NEUQ的谷神要和我赌一个游戏：谷神要求我随机在纸上写出整数集合{1,2,3，…,3n+1}（n是整数）的一个排列（即不重复的随机写出从1到3n+1的所有整数）。
并且要求在我写的过程中，从我写的第一个数开始一直加到我正在写的数的总和不被3整除。如果我能写出来符合要求的一个排列，那么我就赢得游戏。那么问题来了，
我赢得游戏的概率是多少？

输入
一组测试数据，第一行输入测试样例的数目k，接下来k行每行一个正整数n代表一个样例（1<=n<=15）。

输出
对于每个样例数据依次输出我赢得比赛的概率（结果保留小数点后9位有效数字）。

样例输入
1
1

样例输出
0.250000000

提示
例如n=1，则谷神要求我随机写1到4的排列，如果我按顺序写1 3 4 2则是合法的，因为1，1+3、1+3+4、1+3+4+2都不被3整除。如果我按顺序写1 2 3 4则是不
合法的，因为当我写到2的时候1+2=3可以被3整除，不符合游戏规定。

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
int main(){
//  freopen("input.txt","r",stdin);
//  freopen("ouput.txt","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        double ans;
        ans=(n+1.0)/(3*n+1);
        for(int i=1;i<=n;i++) ans*=(double)i/(n+i);
        printf("%.9lf\n",ans); 
    }
    return 0;
}

思路

n!(n+1)!(2n+1)(2n+2)……(3n)/(3n+1)!
公式可化简
注意不能求出分子分母做除法 第15个样例会溢出 卡好的
边求边计算

B

题目要求

删除第三大的数字 输出

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
int a[20];
int main(){
//  freopen("input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    int flag=1;
    while(t--){
        for(int i=1;i<=11;i++) cin>>a[i];
        for(int i=1;i<=3;i++){
            for(int j=2;j<11;j++){
                if(a[j]>=a[j+1]) swap(a[j],a[j+1]);
            }
        }
        cout<<flag++<<" "<<a[9]<<endl;
    }
    return 0;
}

思路

三次冒泡即可
注意输入的第一个数字是组号

C

题目要求

求出区间[a,b]内有多少个菲波拉契数
a和b均为超LL的大数

参考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
import java.util.Scanner;
import java.math.BigInteger;
public class Main{
public static void main(String [] arguments){
    BigInteger [] f=new BigInteger[10001];
    f[1]=BigInteger.ONE;
    f[2]=BigInteger.valueOf(2);
    for(int i=3;i<=10000;i++)
        f[i]=f[i-1].add(f[i-2]);
    Scanner cin = new Scanner(System.in);
    BigInteger l,r;
    l=cin.nextBigInteger();
    r=cin.nextBigInteger();
    while(1>0){
        if(l.equals(BigInteger.ZERO)&&r.equals(BigInteger.ZERO))
            break;
        l=l.add(BigInteger.valueOf(-1));
        int lid=0,rid=0;
        for(int i=1;i<=10000;i++){
            if(f[i].compareTo(l)>0){
                lid=i;
                break;
            }
        }
        for(int i=1;i<=10000;i++){
            if(f[i].compareTo(r)>0){
                rid=i;
                break;
            }
        }
        System.out.println(rid-lid);
        l=cin.nextBigInteger();r=cin.nextBigInteger();
    }
}
}

思路

使用java的大数类水过

D

题目描述
谢尔宾斯基三角形是一种分形，它的构造过程是这样的：
1.取一个实心的三角形。（多数使用等边三角形）
2.沿三边中点的连线，将它分成四个小三角形。
3.去掉中间的那一个小三角形。
4.对其余三个小三角形重复1。
我们想尝试用斜线、反斜线和下划线画出谢尔宾斯基三角，假设最小的三角是长这样的：
/\
/__\
具体规律详见样例。

输入
多组数据输入输出。每行有一个整数n（1<=n<=10），表示执行了一次操作1，n=0时结束输入。

输出
画出执行n次操作1后的图形，调整你的输出到最左端（底边的第一个斜杠在第一列）。输出不能包含任何尾随空格。在每个测试用例后打印空行。

样例输入
3
2
1
0

样例输出

参考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
#include<bits/stdc++.h>
#define N 2050
using namespace std;
int n;
char s[N/2][N];
void print(int x,int y,int d){
    int offset=1<<(d-1);
    if(d==1){
        s[x][y]=s[x+1][y-1]='/';
        s[x][y+1]=s[x+1][y+2]='\\';
        s[x+1][y]=s[x+1][y+1]='_';
        return ;
    }
    print(x,y,d-1);
    print(x+offset, y-offset, d-1);
    print(x+offset, y+offset, d-1);
}
int main(){
//  freopen("input.txt","r",stdin);
//  freopen("ouput.txt","w",sdout);
    while(scanf("%d",&n) && n){
        for(int i=1;i<=(1<<n);i++)
            for(int j=1;j<=(1<<(n+1));j++)
                s[i][j]=' ';
        print(1,(1<<n),n);
        int k=(1<<n)+1;
        for(int i=1;i<=(1<<n);i++,k++){
            for(int j=1;j<=k;j++) putchar(s[i][j]);
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}

思路

谢尔宾斯基三角形
递归输出

E

题目要求

给定一个数组，其中的元素满足非递减顺序。任意给定一个区间[i,j]，求其中某个元素重复出现的最大次数。

参考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
#include<bits/stdc++.h> 
#define MAX_N 500000  
using namespace std;
struct node{  
    int l;  
    int r;  
    int max;  
};  
struct msg{  
    int value;  
    int start;  
    int end;  
};  
node tree[3*MAX_N];  
int a[MAX_N+5];  
int b[MAX_N+5];  
int c[MAX_N+5];  
msg inv[MAX_N+5];    
void build_tree(int left,int right,int root){  
    tree[root].l=left;  
    tree[root].r=right;  
    if(left==right){  
        tree[root].max=b[left];  
        return;  
    }  
    int mid=(left+right)/2;  
    build_tree(left,mid,root*2);  
    build_tree(mid+1,right,root*2+1);  
    tree[root].max=max(tree[root*2].max,tree[root*2+1].max);  
}
int find_max(int left,int right,int root){  
    if(left==tree[root].l&&right==tree[root].r)  
        return tree[root].max;  
    int mid=(tree[root].l+tree[root].r)/2;  
    if(right<=mid)  
        return find_max(left,right,root*2);  
    else if(left>mid)  
        return find_max(left,right,root*2+1);  
    else 
        return max(find_max(left,mid,root*2),find_max(mid+1,right,root*2+1));  
}
int main(){
//  freopen("input.txt","r",stdin);
    int n,m,i,len,inv_len,s,e;  
    while(scanf("%d",&n)!=EOF){  
        if(n==0)  
            break;  
        scanf("%d",&m);  
        for(i=1;i<=n;i++)  
            scanf("%d",&a[i]);  
        len=0,inv_len=0;  
        b[++len]=1;  
        c[1]=1;  
        inv[++inv_len].value=a[1];  
        inv[inv_len].start=1;  
        for(i=2;i<=n;i++){  
            if(a[i]==a[i-1]){  
                b[len]++;  
                c[i]=c[i-1];  
            }  
            else{  
                b[++len]=1;  
                inv[inv_len].end=i-1;  
                inv[++inv_len].value=a[i];  
                inv[inv_len].start=i;  
                c[i]=c[i-1]+1;  
            }  
        }  
        inv[inv_len].end=n;  
        build_tree(1,len,1);  
        for(i=1;i<=m;i++){  
            scanf("%d%d",&s,&e);  
            if(s>e)  
                swap(s,e);  
            int q1=c[s];  
            int q2=c[e];  
            int ans;  
            if(q2-q1==1){  
                int max1=inv[q1].end-s+1;  
                int max2=e-inv[q2].start+1;  
                ans=max(max1,max2);  
            }  
            else if(q2-q1==0){  
                ans=e-s+1;  
            }  
            else{  
                int max1=inv[q1].end-s+1;  
                int max2=e-inv[q2].start+1;  
                int max3=find_max(c[inv[q1].end+1],c[inv[q2].start-1],1);  
                ans=max(max(max1,max2),max3);  
            }  
            printf("%d\n",ans);  
        }  
    }  
    return 0;  
}

参考AC代码(ST)

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
#include<bits/stdc++.h>
using namespace std;  
#define N 100005
#define lowbit(x) (x&-x)    
int n,q;  
int a[N];  
int val[N],cnt[N],num[N],lef[N],righ[N];  
int d[N][50],len;   
void RMQ_init(){ 
    int i,j,k;  
    for(i = 1; i<=len; i++)  
        d[i][0] = cnt[i];  
    for(j = 1; (1<<j)<=len+1; j++)  
        for(i = 1; i+(1<<j)-1<=len; i++)  
            d[i][j] = max(d[i][j-1],d[i+(1<<(j-1))][j-1]);  
}  
int RMQ(int l,int r){ 
    int k = 0;  
    while((1<<(k+1)) <= r-l+1) k++;  
    return max(d[l][k],d[r-(1<<k)+1][k]);  
}   
int main(){ 
//  freopen("input.txt","r",stdin);
    int i,j,k,l,r;  
    while(~scanf("%d",&n),n){
        scanf("%d",&q);  
        len = 1;  
        memset(cnt,0,sizeof(cnt));  
        scanf("%d",&a[1]);  
        val[len] = a[1];  
        cnt[len] = 1;  
        num[1] = len;  
        lef[0] = 1;  
        for(i = 2; i<=n; i++){ 
            scanf("%d",&a[i]);  
            if(a[i]==a[i-1]){
                cnt[len]++;  
                num[i] = len;  
            }  
            else{
                righ[len] = i-1;  
                len++;  
                val[len] = a[i];  
                cnt[len] = 1;  
                num[i] = len;  
                lef[len] = i;  
            }  
        }  
        RMQ_init();  
        while(q--){ 
            scanf("%d%d",&l,&r);  
            if(num[l]==num[r]) printf("%d\n",r-l+1);  
            else{  
                int ans=0;  
                if(num[l]+1<=num[r]-1)  
                    ans=RMQ(num[l]+1,num[r]-1);  
                ans = max(ans,max(righ[num[l]]-l+1,r-lef[num[r]]+1));  
                printf("%d\n",ans);  
            }  
        }  
    }  
    return 0;  
}

转换成RMQ问题 使用线段树或者st模版均可 st更快
因为这个数组是非降序的，所以可以把所有相等的元素组合起来用二元组表示，例如-1,1,1,2,2,2,4就可以表示为(-1,1)(1,2)(2,3)(4,1)，其中(a,b)代表有b个连续的a。
val[i]代表第i段的数值
cnt[i]代表第i段连续的长度
num[i]表示第i个位置的数在那一段
lef[i],righ[i]分别表示第i段的左右端点位置

所求的最大值就是
1.从L到L所在的段的结束处的元素个数：righ[L]-L+1
2.从R到R所在的段的开始处的元素个数：R-lef[R]+1
3.中间第num[L]+1段到第num[R]-1段的cnt的最大值(RMQ)
答案就是1,2,3中的最大值

F

题目描述
存在如下递推式:
F(n+1)=A1F(n)+A2F(n-1)+…+An*F(1)
求第K项的值对1000000007取模的结果

输入
单组测试数据
第一行输入两个整数 n , k (1<=n<=100,n<k<=10000000000)
第二行输入 n 个整数 F(1) F(2) … F(n)
第三行输入 n 个整数A1 A2 … An

输出
输出一个整数

样例输入
2 3
1 2
3 4

样例输出
10

参考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
#include<bits/stdc++.h>
#define maxn 100000
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
struct Matrix{
    LL a[100][100];  
}x,t;  
struct Matrix multiply(int n,struct Matrix a,struct Matrix b){   
    struct Matrix key;  
    mm(key.a,0);
    for(int i=0;i<n;i++){ 
        for(int i1=0;i1<n;i1++){
            if(a.a[i1][i]==0) continue;    //剪枝
            for(int i2=0;i2<n;i2++){  
                key.a[i1][i2]=(key.a[i1][i2]+(a.a[i1][i]*b.a[i][i2])%mod)%mod;  
            }  
        }  
    }  
    return key;  
}  
LL f(int n,LL k){
    while(k){ 
        if(k&1) x=multiply(n,t,x);  
        t=multiply(n,t,t);  
        k>>=1;  
    }  
    return x.a[0][0];  
}  
int main(){
//  freopen("input.txt","r",stdin);
//  freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    LL n,k;
    cin>>n>>k;
    mm(x.a,0),mm(t.a,0);
    for(int i=0;i<n;i++) cin>>x.a[n-i-1][0];
    for(int i=0;i<n;i++){
        cin>>t.a[0][i];
        if(i!=0) t.a[i][i-1]=1;
    }
    cout<<f(n,k-n)<<endl;
    return 0;
}

思路

矩阵快速幂
加个剪枝防tle
下图是n=3时构造的矩阵

构造n维矩阵 快速幂k-n次即可

G

参考AC代码

1
2
3
4
5
6
7
8
9
10
#include<iostream>
using namespace std;
int main()
{
    int n,a[10]={0,8,6,4,4,5,6,5,6,3};
    while (cin >> n){
        cout << a[n] << endl;
    }
    return 0;
}

思路

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

I

题目要求

签到题

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
#include<bits/stdc++.h>
using namespace std;
int main(){
//  freopen("input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    string s;
    cin>>s;
    if(s[0]=='I'&&s[1]=='s') cout<<"Yes, welcome to NEUQ."<<endl;
    else cout<<"What can I do for you?"<<endl;
    return 0;
}

J

题目描述
变位词是指改变某个词的字母顺序后构成的新词。蔡老板最近沉迷研究变位词并给你扔了一道题：
给你一些单词，让你把里面的变位词分组找出来。互为变位词的归为一组，最后输出含有变位词最多的前五组。如果有组数相同的按照字典序输出。

输入
输入包含由小写字母组成的单词，用换行分割，被EOF终止。 输入数据不超过30000个单词。

输出
输出五组包含单词数量最多的变位词，如果少于五组，输出全部。对每组输出，写出它的大小和成员词，成员词按字典序排序用空格分隔，每组输出之间用换行分隔，
相同词只输出一次，但算个数。

样例输入
neuq
tea
bate
beat
caret
trace
nueq
carte
cater
crate
abet
ate
eat
beta
eta
signal

样例输出
Group of size 5: caret carte cater crate trace .
Group of size 4: abet bate beat beta .
Group of size 4: ate eat eta tea .
Group of size 2: neuq nueq .
Group of size 1: signal .

参考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
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define pb push_back
#define LL unsigned long long
#define pii pair<LL,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define maxn 30050
using namespace std;
vector<pii>vec,grop;
vector<int>g[maxn];
int num[30];
string s[maxn];
string st[maxn];
LL Hash(string s){
    LL ans=0;
    mm(num,0);
    for(int i=0;i<(int)s.length();i++) num[s[i]-'a']++;
    for(int i=0;i<26;i++) ans=ans*30+num[i];
    return ans;
}
bool cmp1(pii a,pii b){
    if(a.se==b.se) return st[a.fi]<st[b.fi];
    return a.se>b.se;
}
bool cmp2(const int& a,const int& b){
    return s[a]<s[b];
}
int main(){
//  freopen("input.txt","r",stdin);
//  freopen("ouput.txt","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n=1;
    while(cin>>s[n]){
        LL temp=Hash(s[n]);
        vec.pb(make_pair(temp,n++));
    }
    sort(vec.begin(),vec.end());
//  for(int i=0;i<vec.size();i++) cout<<vec[i].fi<<" "<<vec[i].se<<endl;
    int m=0,cnt=0;
    LL pre;
    g[m].pb(vec[0].se),pre=vec[0].fi,st[m]=s[vec[0].se];
    for(int i=1;i<(int)vec.size();i++){
        if(vec[i].fi==pre){
            g[m].pb(vec[i].se);
            cnt++;
            if(s[vec[i].se]<st[m]) st[m]=s[vec[i].se];
        }
        else{
            grop.pb(make_pair(m,++cnt));
            cnt=0;
            g[++m].pb(vec[i].se);
            pre=vec[i].fi;
            st[m]=s[vec[i].se];
        }
    }
    if(cnt) grop.pb(make_pair(m,++cnt));
    sort(grop.begin(),grop.end(),cmp1);
//  for(int i=0;i<grop.size();i++) cout<<grop[i].fi<<" "<<grop[i].se<<endl;
    for(int i=0;i<min(5,(int)grop.size());i++){
        int index=grop[i].fi;
        sort(g[index].begin(),g[index].end(),cmp2);
//      for(int j=0;j<g[index].size();j++) cout<<g[index][j]<<" "; cout<<endl;
        cout<<"Group of size "<<g[index].size()<<": ";
        for(int j=0;j<(int)g[index].size();j++){
            if(j==0 || s[g[index][j]]!=s[g[index][j-1]]) cout<<s[g[index][j]]<<" ";
        } 
        cout<<".\n";
    }
    return 0;
}

思路

stl硬怼 pair+vector+string
复位词用hash筛选 vec记录下每个单词的hash值以及序号
vec排序后即可把复位词集中在一起 接着考虑按照组内个数分类
既然已经是有序 for遍历一遍即可
grop记录下每组序号和对应的起始位置 降序排序后模拟hash
排序后从头置尾就是最后要输出的组的序列 每组要输出的位置就是grop里的second存储值
g[maxn]则记录每组里的string编号 按照字典序排列后输出即可
注意:
1.for循环后要额外判断是否还有cnt剩余 有的话放去grop里 因为最后一组无法通过比较存入
2.输出的时候注意去重
3.组内元素相同的时候按照每组内字典序最小的单词再按照字典序判断前后顺序
st数组存储的就是每组内字典序最小的位置 for循环里更新维护 在cmp函数里需要比较st数组
4.复位词的hash函数爆LL 用unsigned LL可以确保hash值正确

本文标题:NEUQ-ACM程序设计竞赛(团队赛)

文章作者:Hippopmonkey

发布时间:2017-06-13, 13:52:22

最后更新:2017-06-13, 14:58:20

原始链接:http://xuboming8.github.io/2017/06/13/NEUQ-ACM程序设计竞赛-团队赛/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. NEUQ-ACM程序设计竞赛(团队赛)
    1. 1.1. A
      1. 1.1.1. 参考AC代码
      2. 1.1.2. 思路
    2. 1.2. B
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. C
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. D
      1. 1.4.1. 参考AC代码
      2. 1.4.2. 思路
    5. 1.5. E
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码(线段树)
      3. 1.5.3. 参考AC代码(ST)
    6. 1.6. F
      1. 1.6.1. 参考AC代码
      2. 1.6.2. 思路
    7. 1.7. G
      1. 1.7.1. 参考AC代码
      2. 1.7.2. 思路
    8. 1.8. I
      1. 1.8.1. 题目要求
      2. 1.8.2. 参考AC代码
    9. 1.9. J
      1. 1.9.1. 参考AC代码
      2. 1.9.2. 思路
|