2020.10.18新生赛
A - Multiple of 9
C - Walk on Multiplication Table *
E - Maximal Value *
A、C 、E题为上次比赛原题,所以只做出三道题来的可以好好想想。
B - Where is the Marble?
题意:给你n个数字,再给你m次查询,每次查询一个数字,问你这个数字在所有数字中排第几,如果不存在,输出这个数not found。
思路:这道题我用到了lower_bound(),有三个参数,前两个数查询的区间,第三个参数是要查询的数字x。返回的是大于等于x的地址,如果不存在,则返回最后的区间。如果想要详细了解lower_bound()可以自己从网上找资料。
(跟lower_bound()相对应的是upper_bound(),感兴趣的可以一起学了)
AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; int a[2000005]; int main() { int n,m; int cnt=0; while(cin >> n >> m) { if(n==0 && m==0) break; cout << "CASE# " << ++cnt << ":" << endl; for (int i=1;i<=n;i++) cin >> a[i]; sort(a+1, a+1+n); int x; for (int i=1;i<=m;i++) { cin >> x; int z = lower_bound(a+1, a+1+n, x)-a; if(a[z]!=x) cout << x << " not found" << endl; else cout << x << " found at " << z << endl; } } return 0; }
D - Misha and Changing Handles
题意:
Misha入侵了CF网站,然后他决定让所有的用户更改他们的handles。现在一个用户可以任意多次更改他的handle。但是每一个新的handle一定不能等于以前使用过的handle。
misha有一个更改handle请求的列表,在完成这些请求之后,他想要了解用户们最原先的handle和现在的handle之间的关系,请你帮忙实现它。
输入:
第一行包含一个整数q(1-1e3),代表handle请求改变的数量。接下来q行包含这些请求的描述,每个请求占一行。
每个请求包含两个被一个空格隔开的非空的字符串,一个是老的handle,一个是新的handle。字符串包含大小写的拉丁字母和数字,并且保证新老handle是不同的,而且每个字符串的长度是不超过20的。
思路:简单的map应用,因为是1e3的查询量,所以完全可以用两个for循环进行遍历(第二个for循环是遍历map),具体内容看代码吧。
AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; int a[2000005]; int main() { int n; cin >> n; map<string,string>mp; for (int i=1;i<=n;i++) { string s1,s2; cin >> s1 >> s2; int flag=0; for (map<string,string>::iterator it=mp.begin();it!=mp.end();it++) { if(it->second==s1) { it->second=s2; flag=1; } } if(flag==0) mp[s1]=s2; } cout << mp.size() << endl; for (map<string,string>::iterator it=mp.begin();it!=mp.end();it++) { cout << it->first << " " << it->second << endl; } return 0; }
F - USACO ORZ
题意:
像所有人一样,奶牛也喜欢多样化,现在他们想要的是新的牧场形状,原来的矩形形状已经不受欢迎了。新的几何是最受欢迎。I.M.Hei是奶牛牧场的首席设计师,他负责建造周围有漂亮白色围栏的三角形牧场,他现在有N个围栏段,并且要把他们安排成一个三角形牧场,Ms.Hei必须使用所有的围栏段去建造三角形的三条边(三条边不为0),请你计算不同种类牧场的数量。
如果两个牧场至少一条边不同,则认为这两个牧场是不同的。
思路:N的值最大是15,每段围栏的长度最大是10000,所以所能组成的最大长度是150000,按照三位数储存三条边长,权值分别是1,150000,22500000000,这样用一个set就可以了,用DFS进行寻找,具体思路看代码就可以了,set的find函数比vector的find函数复杂度低,建议用set做这道题。
AC代码:
//为方便起见以后不写头文件了 set<ll>s; int a[2000005]; ll ans,b,c,d; int n; void DFS(int x) { if(x==n+1) { if(b==0||c<b||d<c||b+c<=d) return; if(s.find(b+c*150000+d*22500000000)==s.end()) { s.insert(b+c*150000+d*22500000000); ans++; } return; } b+=a[x]; DFS(x+1); b-=a[x]; c+=a[x]; DFS(x+1); c-=a[x]; d+=a[x]; DFS(x+1); d-=a[x]; } int main() { int t; cin >> t; while(t--) { cin >> n; for (int i=1;i<=n;i++) scanf("%d",&a[i]); s.clear(); ans = 0; b=0;c=0;d=0; DFS(1); printf("%lld\n",ans); } return 0; }
G - Futon *
题意:我们有H*M的矩形网格,每一个网格要么是干净的,要么是脏的,用'.'表示干净,'#'表示脏的,现在让你铺地毯,地毯只能放在相邻的两块干净地毯上,现在问你一共有多少种放地毯的方式。
思路:因为H和M的最大数据只有100,果断暴力。
AC代码:
char a[1005][1005]; int b[1000005]; int main() { int n,m; cin >> n >> m; for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { cin >> a[i][j]; } } ll ans = 0; for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { if(a[i][j]=='.') { if(a[i+1][j]=='.' && i!=n) ans++; if(a[i][j+1]=='.' && j!=m) ans++; } else continue; } } cout << ans << endl; return 0; }
H - Ignatius and the Princess II
题意:
现在我们的英雄找到了通往BEelzebub feng5166的大门,英雄打开了大门并且发现feng5166眼看就要杀了我们漂亮的公主。但是现在BEelzebub不得不先战胜我们的英雄。feng5166说:“我有三个问题问你如果你能够解决他们,我将会放了公主”,Ignatius十分自信地说:“好吧,最后我终将救回公主。”
feng5166说:“现在我给你看第一个问题,给你一个1到n的序列,我们定义1,2,3,···,n-1,n是由所有1到n组成序列中最小的序列(所有的数字当且仅使用一次),所以很容易看出第二小的序列是:1,2,3,···,n,n-1。现在,我将给你两个数,N和M,你需要告诉我由1到n组成的第M小序列,很简单,不是吗?哈哈哈哈哈哈哈哈......”
你能帮助Ignatius解决这个问题吗?
输入:
输入有多组样例,每一组样例有两个数n和m,(n:1-1e3 m:1-1e4)
思路:
用STL里面的next_permutation解
AC代码:
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <stdlib.h> #include <sstream> #include <map> #include <set> typedef long long ll; using namespace std; int a[10000],coun,n,m,i; int main() { while(cin >> n >> m) { for(i=0;i<n;i++) a[i] = i+1; if(m==1) { for (int i=0;i<n-1;i++)cout << a[i] << " "; cout << a[n-1] << endl; continue; //这里不能是return 0,因为是多组输入 } coun = 1; while(next_permutation(a,a+n)) //关于next_permution()的具体用法可以从网上查找 { coun++; if(coun==m) break; } printf("%d",a[0]); for(i=1;i<n;i++) printf(" %d",a[i]); printf("\n"); } return 0; }