ECNU第十届程序设计竞赛

本文主要是介绍ECNU第十届程序设计竞赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Time limit per test: 1.0 seconds

Memory limit: 512 megabytes

几乎每个学 C 语言的人都会面临这样一种困惑：为什么 % 只支持整数和整数，不支持浮点数。自然，C++ 提供了运算符重载几乎可以很方便地实现自定义的浮点数模运算，但到底是不方便的。

而与此相对比的，Java / Python 等高级语言就直接支持了浮点数模运算。

本题就是：给两个浮点数 a, b，求 amodb。

然后你会发现，事情并不简单。

Input

一行两个浮点数 a, b (0<a,b≤109)，a, b 保证保留到小数点后第九位。

Output

输出浮点数，相对误差或绝对误差不超过 10−15。

假设你的答案是 a，标准答案是 b，你的答案正确当且仅当 |a−b|max(1,|b|)<10−15。

Examples

input 
3.000000000 2.000000000
output 
1.000000000

input 
0.400000000 0.200000000
output 
0

看似简单的题，好像就只需要浮点数取个整数倍减一下就好了。

但是由于浮点数的精度不准，存在很大的精度问题。

比赛时候wa了快20遍。（毕竟没做过这类题目）

正解是把浮点数转成整数计算，这样精度就不会损失了。

当然不可能是int,位数不够。所以需要用long long。

先用string读入，再把小数点后位数少的那个数后面的小数点用零补齐。

再存下共有几位小数，计算完毕后再把小数点补上去就可以了。

代码写的比较ugly。懒得

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
int main()
{string s1,s2;cin>>s1>>s2;ll a = 0, b =0;int loc1 = 0, loc2 = 0,len;for(int i = 0; i < s1.length(); i++)if(s1[i] == '.' ){loc1 = i;break;}for(int i = 0; i < s2.length(); i++)if(s2[i] == '.'){loc2 = i;break;}if(s1.length() - loc1 > s2.length() - loc2){int temp = s1.length() - loc1 - (s2.length() - loc2);for(int i = 0; i < temp; i++)s2 = s2 + "0";len = s1.length() - loc1 - 1;}else{int temp = s1.length() - loc1 - (s2.length() - loc2);temp = -temp;for(int i = 0; i < temp; i++)s1 = s1 + "0";len = s2.length() - loc2 - 1;}for(int i = 0; i < s1.length(); i++)if(isdigit(s1[i]))a = a * 10 + s1[i] - '0';for(int i = 0; i < s2.length(); i++)if(isdigit(s2[i]))b = b * 10 + s2[i] - '0';ll ans = a % b;char line[200];sprintf(line, "%lld",ans);int length = strlen(line);string l = string(line);if(length < len){l = "0";for(int i = 0; i < len - length; i++)l = l + "0";l = l + string(line);}//cout<<l<<endl;length = l.length();for(int i = 0; i < l.length(); i++){if(length - i == len){cout<<"."<<l[i];}else cout<<l[i];}cout<<endl;return 0;
}

B. 数螃蟹

Time limit per test: 2.0 seconds

Memory limit: 512 megabytes

kblack 在做数螃蟹的实验。按照「螃蟹爷爷的秘诀」一书上介绍的：由于东方神秘力量的影响，螃蟹的个数是一个完美的等差数列，例如：−2,−1,0,1,2,…。是的，kblack 的螃蟹比较神奇，有的时候螃蟹的个数可能会是负的。

kblack 每天都去池塘记录螃蟹的个数。但是 kblack 自己给自己放了最多三天的假（也有可能两天，有可能一天，有可能不放），放假的时候螃蟹个数的记录就是 kblack 口胡的，有的时候会假得有点过分。

现给出 kblack n 天的记录，记录中至多有三个数是错误的。请纠正错误并输出正确的实验记录。

Input

第一行是一个整数 n (3≤n≤105)。

第二行给出 n 个整数：a1,a2,…,an (|ai|≤109)。

Output

输出正确的实验记录：n 个整数 b1,b2,…,bn。输出应是一个等差数列，与输入的数列至多有三个数不同，且保证 |bi|≤1018。

题目保证有解。如果有多解输出任意一解。

Examples

input 
5
1 2 4 4 5
output 
1 2 3 4 5

input 
4
1 3 5 7
output 
1 3 5 7

input 
4
2 3 3 3
output 
4 3 2 1

虽然有去年数青蛙的阴影，但还是勇敢的开了这道题，最后勇敢的1A了。（虽然全场也就过了这一题）

因为最多只有三个数出错，所以只要枚举前五个数的公差看是否满足条件就可以了。

注意小于4的时候特判，输出四个一样的数。

#include <bits/stdc++.h>
const int maxn = 1e5 + 10;
#define eps 1e15
#define ll long long
using namespace std;
ll a[maxn];
ll b[maxn];
//枚举公差
int main()
{//freopen("in.txt","r",stdin);int n;cin>>n;for(int i = 0; i < n; i++){cin>>a[i];}if(n <= 4){for(int i = 0; i < n; i++)cout<<a[0]<<' ';cout<<endl;return 0;}//如小于n直接输出int cnt;for(int i = 1; i < 5 ; i++){for(int j = 0; j < i; j++){cnt = 0;ll d;if((a[i] - a[j]) % (i - j) == 0)d =(a[i] - a[j]) / (i - j);else continue;//向前修正b[j] = a[j];b[i] = a[i];for(int k = j - 1; k >= 0; k--){if((a[j] - (j - k) * d) != a[k])cnt++;b[k] = a[j] - (j - k) * d;}if(cnt > 3) continue;//向后修正for(int k = j + 1; k < n; k++){if((a[j] + (k - j) * d) != a[k])cnt++;b[k] = a[j] + (k - j) * d;if(cnt > 3) break;}if(cnt <= 3)break;}if(cnt <= 3) break;}for(int i = 0 ; i < n; i++)cout<<b[i]<<' ';cout<<endl;
}

Time limit per test: 3.0 seconds

Memory limit: 1024 megabytes

在面向对象程序设计中，常常会运用到函数的扩展与重写。当一个类继承某个类的时候，它可以调用所有父类可以调用的函数。它可以声明新的函数。当新的函数签名与父类的某个函数一致时，就会发生函数的覆盖（重写）。所以，在子类的实例调用某个函数时，它会调用最近的父类（有可能是它自己）的那个函数实现。

这里我们不考虑访问权限等情况，我们只关心某个类在调用某个函数时，这个函数是在哪个类中实现的。

Input

输入具有如下格式：

np2 p3 … pnt1 a11 a12 … a1t1t2 a21 a22 … a2t2⋮tn an1 an2 … antnqu1 r1u2 r2⋮uq rq

解释与数据规模约定：

n 表示有 n 个类，这些类从 1 到 n 编号。2≤n≤105。
pi 表示第 i 个类的父类编号。1≤pi≤i−1。第 1 个类是所有类共同的祖先类，这个类没有父类。
ti 表示在第 i 个类中定义了多少个函数，ai1,ai2,…,aiti 表示第 i 个类中的函数列表。同一个类的函数列表中不会出现两个相同的函数。1≤aij≤106。0≤ti≤106,∑ti≤106。
q 表示询问个数。1≤q≤105。
ui,ri 表示第 i 个询问，询问第 ui 个类的实例在调用 ri 函数时，调用的是哪个类中的版本。1≤ui≤n,1≤ri≤106。

Output

对于每个询问，输出答案。如果调用不合法（会导致编译错误），输出 −1。

Examples

C题是比赛时候一直在死杠的题，然而用map存最后超内存了。

正解是离线处理。

要存的东西：每个类的子类列表，每个类的函数列表，每个query的问询顺序和结点函数。

然后自顶向下dfs，每次到达一个结点就把这个结点有的函数全部更新为当前结点。

同时把query里关于这个类的query全部处理好（就是对应函数的栈顶元素、可以根据栈的特性得到）

然后回溯的时候把那些函数pop掉就好了。最后输出即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e6 + 10;
using namespace std;
struct query
{int idx,num;query(int a, int b){idx = a;num = b;}
};
vector<query> Q[maxn];//存储所有query
vector<int> son[maxn];//存储每个类的子类
vector<int> cls[maxn];//存储每个类的函数
vector<int> funk[maxn];//函数的栈（用vector模拟）
int ans[maxn];
void dfs(int index)
{for(auto t:cls[index])funk[t].push_back(index);for(auto t:Q[index]){if(funk[t.num].empty())ans[t.idx] = -1;else ans[t.idx] = funk[t.num].back();}for(auto v:son[index])dfs(v);for(auto t:cls[index])funk[t].pop_back();
}
int main()
{int n,q;scanf("%d", &n);for(int i = 2; i <= n; i++){int temp;scanf("%d", &temp);son[temp].push_back(i);//存储每个类的子类}for(int i = 1; i <= n; i++){int T,fun;scanf("%d",&T);while(T--){scanf("%d",&fun);cls[i].push_back(fun);}}scanf("%d", &q);for(int i = 1; i <= q; i++){int k,r;scanf("%d%d", &k, &r);Q[k].push_back(query(i,r));}dfs(1);for(int t = 1; t <= q; t++)cout<<ans[t]<<endl;return 0;
}

这篇关于ECNU第十届程序设计竞赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！