9-28 新生赛预热赛 题解

A – a+b的问题（T组输入）

#include <iostream>

using namespace std;

int a, b;
int main(){
	int T; cin>>T;
	while(T--){
		cin>>a>>b; cout<<a+b<<endl;
	}
	return 0;
}

 

B – 图灵的密码

最简单粗暴的方法：

#include<iostream>
#include<cstdio>
using namespace std;
int main(){
  string s;	
  while(cin>>s){
    cout<<'-';
    for(int i=0;i<s.size();i++)
    switch (s[i]){
      case '0' : cout<<".-----"; break;
      case '1' : cout<<"..----"; break;
      case '2' : cout<<"...---"; break;
      case '3' : cout<<"....--"; break;
      case '4' : cout<<".....-"; break;
      case '5' : cout<<"-....-"; break;
      case '6' : cout<<"--...-"; break;
      case '7' : cout<<"---..-"; break;
      case '8' : cout<<"----.-"; break;
      case '9' : cout<<"------"; break;			
    }		
    cout<<endl;
  }	
  return 0;
}

或者

#include<cstdio>
main(){for(char f,*a="-----.....----";f=~getchar();printf(f+11?"-%.5s":"-\n",a+58+f));}

好孩子不要这么写。

超级好孩子可以写的比这个还短。

C – 绝对素数

会判素数就可以了。基本的语言基础。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

bool isPrime(int t) {
	if(t < 2) return false;
	if(t <= 3) return true;
	for(int i = 2; i * i <= t; i++) {
		if(t % i == 0) return false;
	}
	return true;
}

int reverse(int t) {
	int q = 0;
	while(t) {
		q *= 10;
		q += t % 10;
		t /= 10;
	}
	return q;
}

void exec(int n) {
	int t;
	while(n--) {
		cin>>t;
		if(isPrime(t) && isPrime(reverse(t))) {
			puts("1");
		}else {
			puts("0");
		}
	}
}

int main() {
	for(int n; cin>>n; exec(n));
	return 0;
}

 

D – 面朝大海 春暖花开 [ 数据加强版 ]

看数据范围：1 <= n, m <= 100000。

如果是朴素模拟（在这里就是写二重循环，时间复杂度O(n^2)），最坏的情况下需要操作1e10次，必T。(一般 1e8 就是极限了)

时间复杂度是什么？大O是什么？-> https://blog.csdn.net/so_geili/article/details/53353593

这个题，实际上仍然可以用模拟来做，但是肯定不能用for循环++来模拟了，我们可以用计算的方法。

对于一组最终在[ l , r ]上查询的数据，一次在[c , d] 上的区间种花，有4种情况会出现：

l<=c && d<=r   // 全部在[l,r]内
c<l && r<d     // 完全包含[l,r]
d<l || c>d     // 完全没用
!(d<l || c>d) && !(l<=c && d<=r) //部分包含

（画画图就知道了）

然后计算端点值的差即可。

// 1.50M 28ms
#include <cstdio>
const int N = 100000;
int l[N], r[N];
int main() {
	int n, m;
	while(~scanf("%d %d", &n, &m)) {
		int c, d, fl, fr, ans = 0;
		for(int i = 0; i < m; i++) {
			scanf("%d %d", &l[i], &r[i]);
		}
		scanf("%d %d", &fl, &fr);
		for(int i = 0; i<m; i++) {
			c = l[i];
			d = r[i];
			if(d<fl || c>fr) continue;
			if(d>fr) d = fr;
			if(c<fl) c = fl;
			ans += d - c + 1;
		}
		printf("%d\n",ans);
	}
	return 0;
}

此算法空间复杂度、时间复杂度均为O(n)，需要2n个int，离线算法。此算法适用于1350，上述代码也可AC1350。

也可以用前缀和做，快糙猛。

// 差分 scanf 1.45M 212ms
#include <cstdio>
#include <cstring>
int main() {
	int n, m, t;
	while(~scanf("%d %d %d", &n, &m, &t)) {
		int *a = new int[n+2];
		int c, d;
		memset(a, 0, sizeof(int) * (n+2) );
		while(m--)
			scanf("%d %d", &c, &d),
			a[c]+=1, a[d+1]-=1;
		for(int i=1; i<=n; i++)
			a[i] += a[i-1];
		for(int i=1; i<=n; i++)
			a[i] += a[i-1];
		while(t--)
			scanf("%d %d", &c, &d),
			printf("%d\n",a[d]-a[c-1]);
		delete[] a;
	}
	return 0;
}

 

也可以用st/bit做，不过没啥必要，小题大做了。还慢

不贴代码了，贴了你们也看不懂，看的懂的都不用贴。

E – 整数划分的空间优化问题

很简单的动态规划，二维优化为一维。

为什么不能朴素DFS？->有大量的重复计算，会超时。

动态规划是什么？-> 百度谷歌

如果语言基础还有不足，或基础算法还没有接触过，建议先跳过。

优化前可写为二维DP，优化后一维。原题有点卡常 傻逼行为，时间放宽至2s。

可参考 http://www.voidcn.com/article/p-nwdvvcjj-ng.html

不要在意这种C++写法。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <array>

using namespace std;

const int mod = 100000007;
const int N = 20100;


int main() {
    array<unsigned, N> d;
    d.fill(1);
    for (int i = 2; i <= N; i++) {
        for (int j = i; j <= N; j++) {
            d[j] += d[j - i];
            d[j] %= mod;
        }
    }
    for (int n; cin >> n; cout << d[n] << endl);
    return 0;
}

 

F – Relative Molecular Mass

trie，外加简单的一些类表达式处理。

无非繁琐了一点，难度实际上不高。

代码有点丑。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>

using namespace std;

const int CM = 150;

struct Node {
    double value;
    Node* next[CM];
    Node() { value = 0; memset(next, 0, sizeof(next));};
    void construct(char* s, double value) {
        if (!*s) { this->value = value; return; }
        if (!next[*s]) { next[*s] = new Node();}
        next[*s]->construct(s + 1, value);
    }
} root, *cur;

char *x;

double solve() {
    double ret = 0, val = 0;
    for (; *x != 0 && *x != ')';) {
        if (isalpha(*x)) {
            if (cur->next[*x]) {
                cur = cur->next[*x];
            } else  {
                ret += val;
                val = 0;
                cur = root.next[*x];
            }
            if (cur->value) {
                val = cur->value;
            }
            ++x;
        } else if (isdigit(*x)) {
            int t = 0;
            for (; isdigit(*x); ++x) {t *= 10; t += *x - '0';}
            if (val) {
                ret += val * t;
                val = 0;
                cur = &root;
            } else {
                ret += t * solve();
            }
        } else if (*x == '(') {
            ++x;
            ret += val;
            val = solve();
        }
    }
    ret += val;
    ++x;
    // cout << "RET " << ret << endl;
    return ret;
}

int main() {
    int n, k;
    double v;
    char s[300], t[200];
    memset(root.next, 0, sizeof(root.next));
    scanf("%d%d", &n, &k);
    for (auto i = 0; i < n; i++) {
        scanf("%s%lf", s, &v);
        root.construct(s, v);
    }
    for (auto i = 0; i < k; i++) {
        scanf("%s", t);
        memset(s, 0, sizeof(s));
        int j = 0, c = 0;
        s[c++] = '(';
        for (j = 0; t[j]; j++) {
            if (t[j] == '.') {
                s[c++] = ')';
                s[c++] = '(';
            } else {
                s[c++] = t[j];
            }
        }
        s[c] = ')';
        cur = &root;
        x = s;
        auto ret = solve();
        printf("%.lf\n", ret);
    }
    return 0;
}

 

 

本作品使用基于以下许可授权：Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.