手机网站的开发,进口商品代理平台,免备案服务器推荐,dw做门户网站传送门#xff1a;AtCoder Regular Contest 166 - AtCoder
一直修炼cf#xff0c;觉得遇到了瓶颈了#xff0c;所以想在atcode上寻求一些突破#xff0c;今天本来想尝试vp AtCoder Regular Contest 166#xff0c;但结局本不是很好#xff0c;被卡了半天#xff0c;止步…传送门AtCoder Regular Contest 166 - AtCoder
一直修炼cf觉得遇到了瓶颈了所以想在atcode上寻求一些突破今天本来想尝试vp AtCoder Regular Contest 166但结局本不是很好被卡了半天止步于B题。不过确实感觉AtCoder的题目还是很不错的一改cf的很多惯性思路。
这里借用了大佬樱雪喵的题解链接大佬的传送门如下Atcoder Regular Contest 166 - 樱雪喵 - 博客园 (cnblogs.com)
B - Make Multiples
问题陈述
给你一个整数序列 A(A1,…,AN)以及正整数 ab 和 c。
你可以对这个数列进行以下运算次数不限可能为零。
选择一个整数 i使得 1≤i≤N.将 Ai 替换为 Ai1。
你的目标是使数列 A 至少包含一个 a 的倍数至少一个 b 的倍数以及至少一个 c 的倍数。求实现这一目标所需的最少运算次数。 #includebits/stdc.h
using namespace std;
#define int long long
typedef long long ll;
typedef pairint,int PII;
const int N998244353;
const ll MX0x3f3f3f3f3f3f3f3f;int n,m;
int lcm(int a,int b){return a*b/__gcd(a,b);
}
void icealsoheat(){int a,b,c;cinnabc;vector dp(n5,vector(10,MX));int op[]{1,a,b,lcm(a,b),c,lcm(a,c),lcm(c,b),lcm(lcm(a,c),b)};dp[0][0]0;for(int i0;in;i){int x;cinx;for(int j0;j8;j){for(int k0;k8;k){if((jk)0){// dp[i1][j|k]min(dp[i1][j|k],dp[i][j]op[k])if(x%op[k]0){dp[i1][j|k]min(dp[i1][j|k],dp[i][j]);}else{dp[i1][j|k]min(dp[i1][j|k],dp[i][j](x/op[k]1ll)*op[k]-x);}}}}// coutdp[n][7]\n;}coutdp[n][7]\n;}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_1;// cin_;while(_--){icealsoheat();}
}
C - LU / RD Marking
问题陈述
有一个网格网格中有 H 行和 W 列。
这个网格有H(W1)条垂直边和W(H1)条水平边共计H(W1)W(H1)条(另见输入/输出示例中的数字)。请考虑通过以下两种操作来标记这些边。
操作 (1)**选择一个正方形在进行此操作时其左边缘和上边缘均未标记。标记该正方形的左边缘和上边缘。操作 (2)选择一个右边和下边在执行此操作时没有标记的正方形。标出该正方形的右边和下边。
求操作(1)和操作(2)执行任意多次(可能为零)时最终被标记的边的可能集合的数量模为 998244353998244353。
您有 T 个测试案例需要解决。 这里要借用官方题解的图例 由此将方块拆开找规律。
#includebits/stdc.h
using namespace std;
#define int long long
typedef long long ll;
typedef pairint,int PII;
const int N998244353;
const ll MX0x3f3f3f3f3f3f3f3f;
int n,m;
int dp[2000008];
int sum[2000008];
int kuai(int a,int b){int ans1;while(b){if(b1)ansans*a%N;b1;aa*a%N;}return ans%N;
}
void icealsoheat(){cinnm;if(nm)swap(n,m);int anssum[n]*kuai(dp[2*n],m-n)%N;coutans\n;
}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_1;cin_;dp[0]1;dp[1]2;for(int i2;i2000005;i){dp[i]dp[i-1]dp[i-2];dp[i]%N;}sum[0]1;for(int i1;i1000000;i){sum[i]sum[i-1]*dp[2*i-1]%N*dp[2*i-1]%N;}while(_--){icealsoheat();}
}
D - Interval Counts
因为这题还是比较好想的所以直接上代码
#includebits/stdc.h
using namespace std;
#define int long long
typedef long long ll;
typedef pairint,int PII;
const int N998244353;
const ll MX0x3f3f3f3f3f3f3f3f;
int n,m;
void icealsoheat(){cinn;vectorintx;vectorinty;x.push_back(-2e9);y.push_back(0);for(int i1;in;i){int xx;cinxx;x.push_back(xx);}vectorPIIve;for(int i1;in;i){int xx;cinxx;y.push_back(xx);}ll maxx2e9;int id0;for(int i1;in;i){if(y[i]y[i-1])continue;else if(y[i]y[i-1])ve.push_back({x[i-1]1,y[i]-y[i-1]});else{int nowy[i-1]-y[i];while(idve.size()ve[id].secondnow){maxxmin(x[i]-1-ve[id].first,maxx);now-ve[id].second;id;}if(nowidve.size()){ve[id].second-now;maxxmin(x[i]-1-ve[id].first,maxx);}}}if(maxx1e9)printf(-1\n);else printf(%lld\n,maxx);}
signed main(){ios::sync_with_stdio(false);cin.tie();cout.tie();int _;_1;// cin_;while(_--){icealsoheat();}
}
