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;
}
投递哔哩哔哩等公司10个岗位 >