A.
题解: 快速幂
代码:
- #include<bits/stdc++.h>
- #define ll long long
- #define maxn 100005
- using namespace std;
- const ll mod=2;
- ll b,k;
- ll a[maxn];
- ll fastpow(ll a,ll p)
- {
- ll ans=1;
- while(p)
- {
- if(p&1)ans=ans*a%mod;
- a=a*a%mod;p>>=1;
- }
- return ans;
- }
- int main()
- {
- scanf("%I64d%I64d",&b,&k);
- for(int i=1;i<=k;++i)scanf("%I64d",&a[i]);
- ll n=0;
- for(int i=1;i<=k;++i)n=(n+a[i]*fastpow(b,k-i)%mod)%mod;
- if(n)puts("odd");
- else puts("even");
- }
- View Code
B.
题解: 考虑两两相邻点之间的距离, 贪心取最小的 k-1 个
- #include<bits/stdc++.h>
- #define maxn 100005
- using namespace std;
- int n,m,k;
- int a[maxn];
- priority_queue<int,vector<int>,greater<int>>q;
- int main()
- {
- scanf("%d%d%d",&n,&m,&k);
- int ans=n;
- for(int i=1;i<=n;++i)scanf("%d",&a[i]);
- k=n-k;
- for(int i=1;i<n;++i)q.push(a[i+1]-a[i]-1);
- while(k--)
- {
- int t=q.top();
- q.pop();
- ans+=t;
- }
- printf("%d\n",ans);
- return 0;
- }
- View Code
C.
题解: 找规律, 除了 2^k-1 以外其他情况 ans=2^p-1(其中 p 为满足 ans>a 的最小的数),2^k-1 的情况打表就行
- #include<bits/stdc++.h>
- using namespace std;
- int q;
- int vis[]={0,0,1,1,5,1,21,1,85,73,341,89,1365,1,5461,4681,21845,1,87381,1,349525,299593,1398101,178481,5592405,1082401};
- int main()
- {
- scanf("%d",&q);
- while(q--)
- {
- int a;
- scanf("%d",&a);
- int p=1;
- while(((1<<p)-1)<a)p++;
- if(a==((1<<p)-1))
- {
- if(!vis[p])
- {
- int ans=0;
- for(int b=1;b<a;++b)ans=max(ans,__gcd(a^b,a&b));
- vis[p]=ans;
- printf("%d\n",ans);
- }
- else printf("%d\n",vis[p]);
- }
- else printf("%d\n",(1<<p)-1);
- }
- return 0;
- }
- View Code
D.
题解: 考虑 3 个三元组 [ i-1 ,i ,i+1 ] 可以被拆成[ i-1, i-1, i-1 ] , [ i , i , i ] , [ i+1, i+1, i+1 ], 所以每个状态中这样的三元组不会超过 2 个
然后 dp(i,j,k)表示有 j 个[ i-1 ,i ,i+1 ] , k 个[ i , i+1 , i+2 ], 转移每次枚举一个 l , 表示 dp(i+1,k,l), 其中多 l 个[ i+1 , i+2, i+3 ]
那相同的三元组怎么处理?( num(i) - j -k -l )/3 个, 直接加上就好了
- #include<bits/stdc++.h>
- #define inf 1000000000
- #define maxn 1000005
- using namespace std;
- int n,m;
- int has[maxn];
- int dp[maxn][3][3];
- int main()
- {
- scanf("%d%d",&n,&m);
- for(int x,i=1;i<=n;++i)
- {
- scanf("%d",&x);
- has[x]++;
- }
- for(int i=0;i<=m;++i)
- {
- for(int j=0;j<=2;++j)
- {
- for(int k=0;k<=2;++k)dp[i][j][k]=-inf;
- }
- }
- dp[0][0][0]=0;
- for(int i=0;i<m;++i)
- {
- for(int j=0;j<=min(has[i],2);++j)
- {
- for(int k=0;k<=min(has[i+1],2);++k)
- {
- for(int l=0;l<=min(has[i+2],2);++l)if(has[i+1]>=j+k+l)
- {
- dp[i+1][k][l]=max(dp[i+1][k][l],dp[i][j][k]+l+(has[i+1]-j-k-l)/3);
- }
- }
- }
- }
- printf("%d\n",dp[m][0][0]);
- return 0;
- }
- View Code
E.
题解: 原题, 以前有一道前缀和类似的结论
考虑每次操作, 本质上是在差分数组中交换两个数的位置
我们只需要判断差分数组是否同构以及原数组首尾是否相同就行了
- #include<bits/stdc++.h>
- #define ll long long
- #define maxn 100005
- using namespace std;
- int n;
- ll c[maxn],t[maxn],x[maxn],y[maxn];
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;++i)scanf("%I64d",&c[i]);
- for(int i=1;i<=n;++i)scanf("%I64d",&t[i]);
- if(c[1]!=t[1]||c[n]!=t[n])
- {
- puts("No");
- return 0;
- }
- else
- {
- for(int i=2;i<=n;++i)x[i]=c[i]-c[i-1];
- for(int i=2;i<=n;++i)y[i]=t[i]-t[i-1];
- sort(x+1,x+n+1);
- sort(y+1,y+n+1);
- bool yes=1;
- for(int i=1;i<=n;++i)if(x[i]!=y[i])yes=0;
- if(yes)puts("Yes");
- else puts("No");
- }
- return 0;
- }
- View Code
F,G,H 留坑
来源: http://www.bubuko.com/infodetail-2948950.html