宣武青岛网站建设,苏州正规制作网站公司,百度外包公司有哪些,wordpress酷播loading文章目录 【LittleXi】2023年广东工业大学腾讯杯新生程序设计竞赛A.星期几考试#xff1f;C.信件D、乘除法E、不知道叫什么名字F.我要学会盾反#xff01;G.闪闪发光心动不已#xff01;H.不想想背景的gcdI.uu爱玩飞行棋J.火柴人小游戏K .有趣的BOSS 【LittleXi】2023年广东… 文章目录 【LittleXi】2023年广东工业大学腾讯杯新生程序设计竞赛A.星期几考试C.信件D、乘除法E、不知道叫什么名字F.我要学会盾反G.闪闪发光心动不已H.不想想背景的gcdI.uu爱玩飞行棋J.火柴人小游戏K .有趣的BOSS 【LittleXi】2023年广东工业大学腾讯杯新生程序设计竞赛
[赛题链接](2023年广东工业大学腾讯杯新生程序设计竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com))
A.星期几考试
签到题全部加起来 m o d 7 mod7 mod7就好啦
#includebits/stdc.husing namespace std;#define ll long long
#define endl \nvoid solve(){int n,m;cinnm;mapint,int mp;int time 0;int ac0;for(int i0;im;i){int tp;string cond;cintpcond;if(mp[tp]-1) continue;if(condACmp[tp]!-1){timemp[tp];mp[tp] -1;ac;}elsemp[tp];}coutac timeendl;
}int main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t 1;while(t--){solve();}
}C.信件
脑经急转弯
小心爆int
不难发现每个括号里的数字都是奇数然后如果出现了55乘上任意的奇数末尾都是5
然后发现n等于2的时候出现了5
所以可以分类讨论如下
#includebits/stdc.husing namespace std;#define ll long long
#define endl \nvoid solve(){ll n ;cinn;if(n2ll)cout5endl;elsecout9endl;
}int main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t 1;cint;while(t--){solve();}
}D、乘除法
数学
可以发现5和6互斥
把x看成一堆素数的乘积
那么x中出现的6要大于y中出现的6
x中出现的5要小于y中出现的5
#includebits/stdc.husing namespace std;#define ll long long
#define endl \nvoid solve(){ll x,y;cinxy;ll ans 0 ;ll cnt10,cnt20;ll xx x,yyy;while(xx%60) xx/6,cnt1;while(yy%60) yy/6,cnt2;if(cnt1cnt2) {cout-1endl;return;}for(ll i0;icnt1-cnt2;i){x/6;ans;}while(xy){x*5;ans;}if(xy)coutansendl;elsecout-1endl;
}signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);ll t 1;cint;while(t--){solve();}
}E、不知道叫什么名字
前缀和map
可以把男生看成1女生看成-1
那么就是求一个区间使得区间和为0
可以考虑前缀和做法枚举到 p r e [ i ] pre[i] pre[i]的时候去查找最左边等于 p r e [ i ] pre[i] pre[i]的值不妨记作pre[j]那么因为 p r e [ i ] p r e [ j ] pre[i]pre[j] pre[i]pre[j],所以 p r e [ i ] − p r e [ j ] 0 pre[i]-pre[j]0 pre[i]−pre[j]0区间长度就是 i − j i-j i−j
#includebits/stdc.husing namespace std;#define ll long long
#define endl \nvoid solve(){int n;cinn;vectorint a(n);for(int x:a)cinx;vectorint pre(n,a[0]?1:-1);for(int i1;in;i)pre[i] pre[i-1](a[i]?1:-1);mapint,int mp;mp[0] -1;for(int i0;in;i){if(mp.find(pre[i])!mp.end())continue;mp[pre[i]] i;}int ans 0;for(int i0;in;i){int x pre[i];ans max(ans,i-mp[x]);}coutansendl;
}int main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t 1;while(t--){solve();}
}F.我要学会盾反
盾之勇者成名录
dp数学同余类划分
可以先排序然后可以发现x,x1,x2,x3这样连着的值可以连续地被消除然后x4的时候就陷入了冷却那么什么时候解除冷却呢当然是在x4p*v的点上可以解除冷却
如何快速找到符合条件的x4p*v这个点我们可以发现x4和x4p * v同余所以可以用map记录这个同余类找到后面的那个点之后直接取那个点往后走的最大值类似于dp
遍历的时候可以从大往小遍历
#includebits/stdc.husing namespace std;#define ll long long
#define endl \nvoid solve(){ll n,v;cinnv;vectorll a(n);for(llx:a)cinx;sort(a.begin(),a.end());vectorvectorll vb;vectorll b {a[0]};for(ll i1;in;i){if(b.size()0||a[i]-b.back()1){b.push_back(a[i]);}else{vb.push_back(b);b {a[i]};}}vb.push_back(b);mapll,ll mp;ll di 0;for(ll ivb.size()-1;i0;i--){auto b vb[i];ll r b.back()1;ll w mp[r%v];for(ll jb.size()-1;j0;j--){w;mp[b[j]%v] w;di max(di,w);}}coutn-diendl;
}signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);ll t 1;cint;while(t--){solve();}
}
G.闪闪发光心动不已
dp
题目感觉表述不是很清晰qwq
翻译一个最长子串使得出现若干个kira之后出现若干个doki
可以考虑先从前往后dp求出每个位置前面有多少个kira然后从后往前do求出多少个doki然后拼接起来就行啦
dp的时候可以自己设置一下状态
#includebits/stdc.husing namespace std;#define ll long long
#define endl \n// kirakirakira...dokidokidoki
//状态机dp1
void solve(){int n;cinn;string s;cins;vectorpairint,int dp1(n);string t kira;dp1[0] {0,0};if(s[0] k)dp1[0] {0,1};for(int i1;in;i){dp1[i] dp1[i-1];if(t[dp1[i-1].second]s[i]){if(s[i] a){dp1[i].first1;dp1[i].second 0;}else{dp1[i].second dp1[i-1].second1;}}}vectorpairint,int dp2(n);t ikod;dp2[n-1] {0,0};if(s[n-1] i)dp2[n-1] {0,1};for(int in-2;i0;i--){dp2[i] dp2[i1];if(t[dp2[i1].second]s[i]){if(s[i] d){dp2[i].first1;dp2[i].second 0;}else{dp2[i].second dp2[i1].second1;}}}int ans 0 ;for(int i0;in-1;i){if(dp1[i].firstdp2[i1].first){ansmax(ans,dp1[i].first*4dp2[i1].first*4);}}coutansendl;
}int main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t 1;while(t--){solve();}
}H.不想想背景的gcd
数学
挺有意思的现学了一下辗转相减法
// while (a ! b) {
// if (a b)
// a a - b;
// else
// b b - a;
// }先把a数组倒序排序 g c d ( a 1 b j c k , a 2 b j c k , . . . , a n − 2 b j c k , a n − 1 b j c k ) gcd(a_1b_jc_k,a_2b_jc_k,...,a_n-2b_jc_k,a_n-1b_jc_k) gcd(a1bjck,a2bjck,...,an−2bjck,an−1bjck)
等价于 g c d ( a 1 − a 2 , a 2 − a 3 , . . . , a n − 2 − a n − 1 , a n − 1 b j c k ) gcd(a_1-a_2,a_2-a_3,...,a_n-2-a_n-1,a_n-1b_jc_k) gcd(a1−a2,a2−a3,...,an−2−an−1,an−1bjck)
因为根据辗转相减法$gcd(a_1p,a_2p) $ g c d ( a 1 − a 2 , a 2 p ) gcd(a_1-a_2,a_2p) gcd(a1−a2,a2p)
由gcd的结合律我们可以对每项都使用这个技巧就化完了
对于上面式子再次由gcd结合律可以得到 g c d ( a 1 − a 2 , a 2 − a 3 , . . . , a n − 2 − a n − 1 , a n − 1 b j c k ) gcd(a_1-a_2,a_2-a_3,...,a_n-2-a_n-1,a_n-1b_jc_k) gcd(a1−a2,a2−a3,...,an−2−an−1,an−1bjck) g c d ( g c d ( a 1 − a 2 , a 2 − a 3 , . . . , a n − 2 − a n − 1 ) , a n − 1 b j c k ) gcd(gcd(a_1-a_2,a_2-a_3,...,a_n-2-a_n-1),a_n-1b_jc_k) gcd(gcd(a1−a2,a2−a3,...,an−2−an−1),an−1bjck)
前面n-1项可以预处理出来后面b,c可以直接枚举
小心卡常
#includebits/stdc.husing namespace std;#define ll long long
#define endl \ninline ll gcd(ll x, ll y) {return y 0 ? x : gcd(y, x % y);
}void solve(){ll n;cinn;vectorll a(n),b(n),c(n);for(ll x:a) cinx;for(ll x:b) cinx;for(ll x:c) cinx;ll g 0;sort(a.begin(),a.end());reverse(a.begin(),a.end());for(ll i0;in-1;i){g gcd(g,a[i]-a[i1]);}ll an_1 a[n-1];ll mx 0,mi 2e18;for(ll i0;in;i){for(ll j0;jn;j){ll ng gcd(g,an_1b[i]c[j]);mx max(mx,ng);mi min(mi,ng);}} coutmi mxendl;
}signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);ll t 1;while(t--){solve();}
}I.uu爱玩飞行棋
背包dp
非常经典的背包可以发现距离只有1000
维护一个长度为1010的背包dp[i]表示到达这个位置花费的最少的骰子
然后枚举骰子从左往右维护每个点
#includebits/stdc.husing namespace std;#define ll long long
#define endl \nvoid solve(){int n,m;cinnm;vectorint a(m);for(intx:a)cinx;vectorint dp(n10,2*m);dp[9] 0;int tar 10n-1;for(int i0;im;i){auto tdp dp;for(int j0;jtar;j){int to j a[i];if(to tar){to tar-(to-tar);}tdp[to] min(tdp[to],dp[j]1);}dp tdp;}if(dp[tar]2*m){cout-1endl;}elsecoutdp[tar];
}int main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t 1;while(t--){solve();}
}J.火柴人小游戏
贪心优先队列
很多同学直接二分check但是我没想出来 O ( n m ) O(nm) O(nm)的check这样复杂度就是 O ( n m l g 2 ( n m ) ) O(nmlg^2(nm)) O(nmlg2(nm))了导致TLE
我没可以直接bfs当从优先队列中取出来的点大于了当前的能量值我们就我们我们自己的能量值增加一点使得能打败当前的敌人其实就是贪心
时间复杂度 O ( n m l g ( n m ) ) O(nmlg(nm)) O(nmlg(nm))
#includebits/stdc.h
using namespace std;#define ll long long
#define endl \nll n,m,x,y;
ll grid[1005][1005] {0};
ll vis[1005][1005] {0};
bool ifon(ll x,ll y){return x0xny0ym;
}ll cal(ll md){ll ans md;for(ll i0;in;i)for(ll j0;jm;j)vis[i][j] 0;vis[x][y] 1;priority_queuepairll,pairll,ll,vectorpairll,pairll,ll,greaterpairll,pairll,ll pq;pq.push({0,{x,y}});ll dx[4] {-1,1,0,0};ll dy[4] {0,0,-1,1};ll arr 0;while(pq.size()){auto pp pq.top();pq.pop();if(mdpp.first){ans pp.first-md;md pp.first;}arr 1;md pp.first;ll nx pp.second.first,ny pp.second.second;for(ll i0;i4;i){ll tox dx[i]nx;ll toy dy[i]ny;if(!ifon(tox,toy)) continue;if(vis[tox][toy]) continue;vis[tox][toy] 1;pq.push({grid[tox][toy],{tox,toy}});}}return ans;
}void solve(){cinnmxy;x--;y--;for(ll i0;in;i)for(ll j0;jm;j) cingrid[i][j];ll st grid[x][y];grid[x][y] 0;ll ans cal(st);if(ans st){coutNo cheating need.endl;} elsecoutansendl;
}signed main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);ll t 1;while(t--){solve();}
}K .有趣的BOSS
素数分解思维
1、要么/2 2、要么刚好砍到0 3、那么就是每一步判断有没有机会刚好砍到0 4、直接从n中取出某个素数并且把这种素数取完得到l剩下的是n/l,然后计算ln/l是否小于等于n如果是这样的话怪兽二受到n点伤害怪兽1收到ln/l点伤害不够怎么办呢没事直接补1补到n为止
5、如果4不行那么直接用很多很强的到把两只都砍到0以下
#includebits/stdc.husing namespace std;#define ll long long
#define endl \nvoid solve(){int n;cinn;int cnt 0;while(n){if(n1){coutcnt1endl;return;}for(int i2;i*in;i){if(n%i0){int ts 0;int nn n;int l 1;while(nn%i0) ts,nn/i,l*i;if(lnnn){coutcnt1endl;return;}else break;}}n1;cnt;}
}int main(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);int t 1;cint;while(t--){solve();}
}
