A
solution:
题意和icpc-final签到题相似呀
可将面积等于一的三角形分为下面五种情况：
1.两条边均平行x或y轴的；
2.一条边平行x轴，底为2、高为1
3.一条边平行x轴，底为1、高为2
4.一条边平行y轴，底为2、高为1
5.一条边平行y轴，底为1、高为2
第一种即以2*3点阵为最小单位，每个点阵中有四个好三角形
第二种即求出2 * m点阵中的底为2、高为1的好三角形，再乘上n - 1行
第三种即求出3 * m点阵中的底为1、高为2的好三角形，再乘上n - 2行
第四、五种。。。。
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod = 1e9+7;
int main()
{
ll n , m;
cin>>n>>m;
if(n == 2 && m == 2){
printf("0");
return 0;
}
ll ans = 0;
ans = (n-1)*(m-2)*4%mod+(n-2)*(m-1)*4%mod;
ans = (ans+2*(m-2)*(n-1)%mod*(m-2)%mod + 2*(n-2)*(m-1)%mod*(n-2)%mod)%mod;
ans = (ans+2*(m-1)*(n-2)%mod*(m-2)%mod + 2*(n-1)*(m-2)%mod*(n-2)%mod)%mod;
cout<<ans<< endl;
return 0;
}
B
solution:
签到题之一
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
double n,x,a,b;
cin>>n>>x>>a>>b;
double ans1 = n*a;
double ans2 = n*b;
double ans = ans1*(x/100) + ans2*((100-x)/100);
printf("%.2lf\n",ans);
return 0;
}C
solution:
计算几何，没写出来，赛后补的
首先同一个象限的肯定无法阻挡，剩下的点分别找到和x，y轴的交点，存到两个数组
记得用double，然后只需要用双指针移动窗口维护一个区间最短长度即可
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector< double > vx,vy;
int main()
{
int n,k;
double x,y,x1,y1,x2,y2;
cin>>x1>>y1>>n>>k;
k = n - k;
for(int i=1;i<=n;i++){
cin>>x>>y;
if(x*x1 < 0){
vy.push_back(y1 - x1*(y-y1)/(x-x1));
}
if(y*y1 < 0){
vx.push_back(x1 - y1*(x-x1)/(y-y1));
}
}
double ans = 1e18;
sort(vx.begin(),vx.end()),sort(vy.begin(),vy.end());
if(vx.size() >= k)
{
double l = 0,r = k-1;
while(r < vx.size()){
ans = min(ans , vx[r] - vx[l]);
l++,r++;
}
}
if(vy.size() >= k){
double l = 0,r = k-1;
while(r < vy.size()){
ans = min(ans , vy[r] - vy[l]);
l++,r++;
}
}
if(ans == 1e18)
printf("-1\n");
else
printf("%.8lf\n",ans);
return 0;
}
D
solution:
直接用数组或者map存一下每一碗米饭数量，遍历一遍即可
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
int n,x;
map<int , int> mp;
cin>>n;
for(int i=1;i<n;i++){
cin>>x;
mp[x] = 1;
}
int ans = 0;
for(int i=1;i<=n;i++){
if(mp[i] == 0){
ans = i;
break ;
}
}
cout<<ans<<endl;
return 0;
}E
solution:
直接O(sqrt(n))遍历一遍即可，迭代次数很少，我还傻傻的判了个大素数
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll mod_exp(ll a,ll b,ll n)//快速幂取模
{
ll m=1;
while(b)
{
if(b&1) m=(m%n)*(a%n)%n;
b>>=1;
a=(a%n)*(a%n)%n;
}
return m;
}
bool miller_rabbin(ll n)
{
ll i,a;
for(i=0;i<50;i++)
{
a=rand()%(n-2)+2;
if(mod_exp(a,n-1,n)!=1)
return false;
}
return true;
}
int main()
{
ll n ;
cin>>n;
if(miller_rabbin(n)){
printf("1\n");
return 0;
}
int ans = 0;
while(1)
{
ll cnt = 2;
ans++;
for(ll i=2;i*i<=n;i++)
{
if(n%i == 0){
if(n/i == i)
cnt++;
else{
cnt+=2;
}
}
}
n = cnt ;
if(n == 2){
break;
}
}
printf("%d\n",ans);
return 0;
}F
solution:
多么好的一道并查集，第一眼看成了树上dp
先说明一下我的思路，上图：
我们首先将所有相邻的白色节点归入并查集，即1，2，3，4四个不同的集合
然后我们只需要遍历所有的黑色节点，找到他们相邻的所有白色节点的集合
我们看最中间的那个黑色节点，找到所有和它相连的白色集合，即1，2，3，4
这个节点对答案做出的贡献 = 分别和1，2，3，4相连 + 1和2相连 + 1和3相连 + 1和4相连 + 2和3相连 + 2和4相连 + 3和4相连再不理解我可真没办法了
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 100005;
int f[maxn];
vector<int> v[maxn];
char s[maxn];
int a[maxn],b[maxn];
int find(int x)
{
return x == f[x] ? x : f[x] = find(f[x]);
}
void unite(int x,int y)
{
x = find(x);
y = find(y);
if(x != y){
f[x] = y;
}
return ;
}
map<int , int> mp;
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
f[i] = i;
}
scanf("%s",s+1);
for(int i=1;i<=n;i++)
{
if(s[i] == 'B')
a[i] = 1;
}
int x,y;
for(int i=1;i<n;i++){
scanf("%d %d",&x,&y);
if(a[x] == 0 && a[y] == 0){
unite(x,y);
}
v[x].push_back(y);
v[y].push_back(x);
}
for(int i=1;i<=n;i++){
int x = find(i);
mp[x]++;
}
ll ans = 0;
for(int i=1;i<=n;i++)
{
if(a[i] == 1){
int cnt = 0;
int siz = v[i].size();
for(int j=0;j<siz;j++)
{
int x = v[i][j];
if(a[x] == 1){
continue ;
}
b[++cnt] = mp[find(x)];
}
ans += b[cnt];
for(int j=1;j<cnt;j++){
ans += 1ll*(b[j]);
for(int k=j+1;k<=cnt;k++){
ans += 1ll*(b[j]*b[k]);
}
}
}
}
printf("%lld\n",ans);
return 0;
}G
solution:
尺举连续的k个相同字母的距离即可，先存一下每个字母的位置，然后遍历26个字母
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 200005;
int n,k;
char s[maxn];
vector<int> v[50];
int main()
{
scanf("%d %d",&n,&k);
scanf("%s",s+1);
for(int i=1;i<=n;i++){
v[s[i]-'a'].push_back(i);
}
int maxx = 0;
for(int i=0;i<26;i++){
int z = v[i].size();
maxx = max(maxx , z);
}
if(maxx < k){
printf("-1");
return 0;
}
int ans = 1e9;
for(int i=0;i<26;i++){
if(v[i].size() < k){
continue ;
}
int minn = v[i][k-1] - v[i][0] + 1;
for(int j=k;j<v[i].size();j++){
minn = min( minn , v[i][j] - v[i][j-k+1] + 1);
}
ans = min(ans , minn);
if(ans == k){
break ;
}
}
printf("%d",ans);
return 0;
}H
solution:
分别处理两种操作即可。对于1变0的情况，可以分别统计每个1的前缀1和后缀1的位置（第一个1的前缀为 0 ，最后一个1的后缀为n+1 ），k 次操作，即变换连续k个1，最终的字符串长度就是第i个1的前缀1到第i+k个后缀1之间的距离。0的情况也是这样
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 200005;
char s[maxn];
int a[maxn][2],b[maxn][2];
vector<int> v[3];
int main()
{
int n,k,cnt1 = 0,cnt0 = 0;
scanf("%d %d",&n,&k);
scanf("%s",s+1);
int sum1 = 0,sum2 = 0;
for(int i=1;i<=n;i++)
{
if(s[i] == '1'){
sum1++;
}else{
sum2++;
}
v[s[i]-'0'].push_back(i);
if(s[i] == '1'){
a[i][0] = cnt0;
a[i][1] = cnt1;
cnt1++;cnt0 = 0;
}
else{
a[i][0] = cnt0;
a[i][1] = cnt1;
cnt0++;cnt1 = 0;
}
}
if(min(sum1 ,sum2) <= k){
printf("%d",n);
return 0;
}
cnt1 = cnt0 = 0;
for(int i=n;i>=1;i--)
{
if(s[i] == '1'){
b[i][0] = cnt0;
b[i][1] = cnt1;
cnt1++;cnt0 = 0;
}
else{
b[i][0] = cnt0;
b[i][1] = cnt1;
cnt0++;cnt1 = 0;
}
}
int ans = 1;
int ans1 = v[0][k-1] - v[0][0] + 1 + b[v[0][k-1]][1] + a[v[0][0]][1];
for(int i=k;i<v[0].size();i++)
{
int cnt = v[0][i] - v[0][i-k+1] + 1 + b[v[0][i]][1] + a[v[0][i-k+1]][1];
ans1 = max(ans1 , cnt);
}
int ans2 = v[1][k-1] - v[1][0] + 1 + b[v[1][k-1]][0] + a[v[1][0]][0];
for(int i=k;i<v[1].size();i++)
{
int cnt = v[1][i] - v[1][i-k+1] + 1 + b[v[1][i]][0] + a[v[1][i-k+1]][0];
ans2 = max(ans2 , cnt);
}
ans = max(ans , max(ans1 , ans2));
cout<<ans<<endl;
return 0;
}I
solution:
明显这是个dp，状态转移方程看公式，记得数组开long long
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[300005];
int main()
{
ll n,x,y,z;
string s;
cin>>n>>x>>y>>z;
cin>>s;
for(int i=0;i<n;i++){
if(i > 0)
dp[i] = dp[i-1];
if(i >= 3 && s[i-3] == 'n' && s[i-2] == 'i' && s[i-1] == 'c' && s[i] == 'o')
dp[i] = max(dp[i] , dp[i-3] + x);
if(i >= 5 && s[i-5] == 'n' && s[i-4] == 'i' && s[i-3] == 'c' && s[i-2] == 'o' && s[i-1] =='n' && s[i] == 'i')
dp[i] = max(dp[i] , dp[i-5] + y);
if(i >= 9 && s[i-9]=='n'&&s[i-8]=='i'&&s[i-7]=='c'&&s[i-6]=='o'&&s[i-5]=='n'&&s[i-4]=='i'&&s[i-3]=='c'&&s[i-2]=='o'&&s[i-1]=='n'&&s[i]=='i')
dp[i] = max(dp[i] , dp[i-9] + z);
}
printf("%lld\n",dp[n-1]);
return 0;
}J
solution:
这一题需要用到的数论知识包括：费马小定理and矩阵快速幂
费马小定理可以简单理解为：
对于计算a^b%p ，而且p为素数，则有a^b%p = a^(b%(p-1))%p
矩阵快速幂：
矩阵快速幂和快速幂实质都是简化时间复杂度，时间复杂度都是log(n)
如果对矩阵快速幂还不熟悉，建议先学习一下如何使用矩阵快速幂，学过线性代数掌握起来会快一点。
如果对矩阵快速幂还不熟悉，建议先学习一下如何使用矩阵快速幂，学过线性代数掌握起来会快一点。
显然 f(n) 可以用 x , y 和 a 这三个因子表达出来。每一项a的幂次分别是 0、0、b、2b、4b、7b、12b……从第三项开始每一项为前两项之和加1。而x和y的幂次构成斐波那契数列：x的幂次第一项是1，第二项是0；y的幂次第一项是0，第二项是1。之后每一项均为前两项之和。
具体看代码，这道题目，无非是需要多写几个矩阵快速幂，但是一定要记得如果费马小定理和矩阵快速幂一起用的时候取模的哪些部分应该取mod-1，哪些应该取mod！
std:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll pow_mod(ll a,ll b,ll mod)
{
ll ans = 1;
while(b){
if(b&1)
ans = ans*a%mod;
a = a*a%mod;
b>>=1;
}
return ans;
}
const ll mod = 1e9 + 7;
struct node{
ll m[2][2];
node(){
memset(m,0,sizeof(m));
}
friend node operator *(node a,node b){
node ans;
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
ans.m[i][j] = (a.m[i][k]*b.m[k][j] + ans.m[i][j])%(mod-1);
return ans;
}
friend node pow(node a,ll k){
node ans;
ans.m[0][0] = ans.m[1][1] = 1,ans.m[0][1] = ans.m[1][0] = 0;
while(k){
if(k&1)
ans = ans*a;
a = a*a;
k >>= 1;
}
return ans;
}
};
struct node2{
ll m[3][3];
node2(){
memset(m,0,sizeof(m));
}
friend node2 operator *(node2 a,node2 b){
node2 ans;
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
for(int k=0;k<3;k++)
ans.m[i][j] = (a.m[i][k]*b.m[k][j] + ans.m[i][j])%(mod-1);
return ans;
}
friend node2 pow(node2 a,ll k){
node2 ans;
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
if(i == j)
ans.m[i][j] = 1;
else
ans.m[i][j] = 0;
}
}
while(k){
if(k&1)
ans = ans*a;
a = a*a;
k >>= 1;
}
return ans;
}
};
ll solve1(ll x)
{
node a,ans;
a.m[0][0] = a.m[0][1] = a.m[1][0] = 1 ,a.m[1][1] = 0;
ans = pow(a , x);
return ans.m[0][1];
}
ll solve2(ll x)
{
node a,ans;
a.m[0][0] = a.m[0][1] = a.m[1][0] = 1 ,a.m[1][1] = 0;
ans = pow(a , x);
return ans.m[0][0];
}
ll solve3(ll x)
{
node2 a,ans;
a.m[0][0] = a.m[0][1] = a.m[0][2] = a.m[1][0] = a.m[2][2] = 1;
a.m[1][1] = a.m[1][2] = a.m[2][0] = a.m[2][1] = 0;
ans = pow(a , x);
return ans.m[0][2];
}
int main()
{
ll n , x , y , a, b;
cin>>n>>x>>y>>a>>b;
if(n == 1){
printf("%lld\n",x%mod);
return 0;
}
if(n == 2){
printf("%lld\n",y%mod);
return 0;
}
if(x%mod == 0 || y%mod == 0 || a%mod == 0){
printf("0\n");
return 0;
}
a = pow_mod(a%mod , b , mod);
ll ans = pow_mod(x%mod , solve1(n-2) , mod)%mod*pow_mod(y%mod , solve2(n-2) , mod)%mod*pow_mod(a%mod , solve3(n-2)%(mod-1) , mod)%mod;
cout<<ans<<endl;
return 0;
}
京公网安备 11010502036488号