A ABC Swap
题意：依次交换AB,AC中的元素，输出最后结果
如果实在懒得想就像我一样看着题写两个swap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define db double
#define ld long double
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#pragma GCC optimize(2)
#define ull unsigned long long
#define maxn 1020
signed main()
{
IOS
int x,y,z;
cin>>x>>y>>z;
swap(x,y);
swap(x,z);
cout<<x<<" "<<y<<" "<<z;
return 0 ;
}
|
B Popular Vote
题意：N个物品，每个都有一个权值，询问是否存在M个物品，其中每个物品的权值不小于权值和的$\frac{1}{4M}$
先算出总和，然后O(N)遍历，一个简单的移项可以帮助你避免浮点数的使用
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
| #include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define db double
#define ld long double
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#pragma GCC optimize(2)
#define ull unsigned long long
#define maxn 110
ll lcm(ll a,ll b){return a*b/__gcd(a,b);}
void dfs(){}
int a[maxn];
signed main()
{
IOS
int n,m;
ll sum=0;
cin>>n>>m;
for (int i = 0; i <n ; ++i) {
cin>>a[i];
sum+=a[i];
}
int cnt=0;
for (int j = 0; j <n ; ++j) {
if(a[j]*4*m>=sum)cnt++;
}
if(cnt>=m)cout<<"Yes";
else cout<<"No";
return 0 ;
}
|
C Replacing Integer
题意：给你N和K，每次可以把N替换为N和K差的绝对值，询问所有替换中N的最小值
很简单的一道思维题，如果N大于K，那么N就可以写成M*K+b的形式，而如果N小于等于K,N会在N和K-N之间反复横跳，那么我们只需要去找N%K和K-N%K之中的最小值即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define db double
#define ld long double
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#pragma GCC optimize(2)
#define ull unsigned long long
#define maxn 110
int a[maxn];
ll n,k;
signed main()
{
IOS
cin>>n>>k;
if(n%k==0)cout<<0;
else{
n%=k;
cout<<min(n,k-n);
}
return 0 ;
}
|
D Lunlun Number
题意：lunlun数的定义是该数字每一位与相邻位差的绝对值小于等于1，求第k小的lunlun数
二维dp，一开始想的打表，但实在太懒，就去搞dp了，而范围也不用太大，差不多10*10的二维数组，dp[i][j]表示当前数字有i位，然后首位数字为j的方案数，然后转移的时候就很好转移了，只需要在dp[i-1][j-1],dp[i-1][j],dp[i-1][j+1]三者里找到合法的项加上即可。求出来之后怎么办呢，依次遍历每一项，如果K小于等于当前的dp值，那么要找的数一定在这个状态里，否则K-当前的dp值，继续遍历。
当我们找到dp[i][j]>=K的情况时，只需要在i-1的情况里继续找即可，只不过每次第二维被限制在j-1,j,j+1，当第一维为0时输出即可。
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
| #include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define db double
#define ld long double
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#pragma GCC optimize(2)
#define ull unsigned long long
#define maxn 110
int dp[maxn][maxn];
signed main()
{
IOS
int num;
cin>>num;
memset(dp,0, sizeof(dp));
for (int k = 0; k <=9 ; ++k) {
dp[1][k]=1;
}
for (int i = 2; i <=10 ; ++i) {
for (int j = 0; j <=9 ; ++j) {
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j+1];
}
}
queue<int> ans;
int l=0, r = 0,fl=0;
for (int j = 1; j <=10 ; ++j) {
for (int i = 1; i <=9 ; ++i) {
if(num<=dp[j][i]){
l=j;
r=i;
fl=1;
break;
}
num-=dp[j][i];
}
if(fl==1)break;
}
l--;
ans.push(r);
while(l!=0){
if(num<=dp[l][r-1]){
r--;
ans.push(r);
}else{
num-=dp[l][r-1];
if(num<=dp[l][r]){
ans.push(r);
}else{
num-=dp[l][r];
r++;
ans.push(r);
}
}
l--;
}
while(!ans.empty()){
int now=ans.front();
cout<<now;
ans.pop();
}
return 0 ;
}
|
E Yutori
题意：Takahashi需要选择K天工作，如果某一天他工作了，那么之后C天都不用工作，同时存在一些日子，这些日子里他不用工作，询问在所有的挑选方案里，哪一天必须工作？
这道题比赛没切出来（我是屑 )，看完大佬代码之后，发现是一道贪心水题，我们先记录Takahashi最勤快的情况（尽量早地完成工作）是哪几天，最懒惰的情况（与前者相反）是哪几天，然后去找交集，如果某个元素在二者中都出现且位次一致，那么这天就是必须工作的。
为什么贪心是对的呢？
这里说一说本蒟蒻的思路：
首先如果某一天必须工作，那么它一定出现在最勤快和最懒惰的情况，那么交集是肯定正确的。那么位次不同为什么就不合法呢？我们假设最勤快的情况是1、3、5，最懒惰的情况是3、5、7，交集是3、5，但是我们可以取1、5、7（不取3），也可以取1、3、7（不取5），显然只有交集中位次相同的才是对的。
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
| #include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define db double
#define ld long double
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#pragma GCC optimize(2)
#define ull unsigned long long
#define maxn 200005
int l[maxn],r[maxn];
signed main()
{
IOS
int n,k,c;
string s;
cin>>n>>k>>c;
cin>>s;
int cnt=0;
memset(l,-1, sizeof(l));
memset(r,-1, sizeof(r));
for (int i = 0; i <n&&cnt<k ; ++i) {
if(s[i]=='x')continue;
else{
l[cnt++]=i;
i+=c;
}
}
cnt=k-1;
for (int j = n-1; j >=0&&cnt>=0 ; --j) {
if(s[j]=='x')continue;
else{
r[cnt--]=j;
j-=c;
}
}
for (int m = 0; m <k ; ++m) {
if(l[m]==r[m]&&l[m]!=-1)cout<<l[m]+1<<endl;
}
return 0 ;
}
|
F Division or Substraction
题意：在2~N之间选一个数，然后进行下列操作：
- 如果N模K等于0，将N替换为N/K
- 如果N模K不为0，将N替换为N-K
求可以使N变成1的K的取值方案数
数论水题啦，一开始的思路分的情况有点多，听了学长的思路发现部分方案可以合并，如下：
很容易可以想到一种合法的情况是一直除到1，还有一种情况是先除再减，即对每一个合法的k，我么都可以把n写成下面的形式$${k^p}{(ak+1)}$$其中p>=0,a>=0并且二者不同时为0（1不合法），那么只需要分别讨论p为0和不为0的情况就好，为0几乎就是求n-1的因子数了，$\sqrt{N}$的时间可以解出来，另一种情况其实也可以在相同的时间复杂度内解出来，因为p不为0时，只有a=0时，式子中才不会出现${k^2}$，容易解出大于$\sqrt{N}$的范围内只有N时满足题意的，只需要枚举2~$\sqrt{N}$即可。
（合并方案后用时竟然从四位数快到了两位数）
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
| #include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define db double
#define ld long double
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#pragma GCC optimize(2)
#define ull unsigned long long
#define maxn 110
signed main()
{
IOS
ll n;
cin>>n;
ll ans=1;
for (ll i = 2; i <=(ll)sqrt(n) ; ++i) {
ll now=n;
while(now%i==0){
now/=i;
if((now-1)%i==0){
ans++;
break;
}
}
}
n--;
for (ll l = 1; l <=(ll)sqrt(n) ; ++l) {
if(n%l==0){
ans+=2;
if(l==1)ans--;
if(l*l==n)ans--;
}
}
cout<<ans;
return 0 ;
}
|