1[CSP-J 2024] 小木棍
错因：bfs暴力本身就有问题,时间和空间肯定过不了，不过思路是正确的,题目特性也暗示了7的倍数
正确做法：
#include<bits/stdc++.h>
using namespace std;
//0 1 2 3 4 5 6 7 8 9
//6 2 5 5 4 5 6 3 7 6
int main(){
int t;
cin>>t;
//思路：
//可以发现8用的棍数最多，所以8越多，位数越少，值越少
//所以尽量多凑8出来
while(t--){
int n;
cin>>n;
if(n==1)cout<<-1<<'\n';
//可以手动推出n为1-9时的最小值
else if(n==2)cout<<1<<'\n';
else if(n==3)cout<<7<<'\n';
else if(n==4)cout<<4<<'\n';
else if(n==5)cout<<2<<'\n';
else if(n==6)cout<<6<<'\n';
else if(n==7)cout<<8<<'\n';
//10要特别判断，因为最小值并不是78
else if(n==10)cout<<22<<'\n';
//后续通过计算%7(8的用棍数为7)后的余数，计算用棍数为余数的最小值
//再加上剩下整除7的次数的8
else if(n%7==0){
for(int i=1;i<=n/7;i++){
cout<<8;
}
cout<<'\n';
}else if(n%7==1){
cout<<10;
for(int i=1;i<=(n-8)/7;i++){
cout<<8;
}
cout<<'\n';
}else if(n%7==2){
cout<<1;
for(int i=1;i<=(n-2)/7;i++){
cout<<8;
}
cout<<'\n';
}else if(n%7==3){
cout<<200;
for(int i=1;i<=(n-17)/7;i++){
cout<<8;
}
cout<<'\n';
}else if(n%7==4){
cout<<20;
for(int i=1;i<=(n-11)/7;i++){
cout<<8;
}
cout<<'\n';
}else if(n%7==5){
cout<<2;
for(int i=1;i<=(n-5)/7;i++){
cout<<8;
}
cout<<'\n';
}else if(n%7==6){
cout<<6;
for(int i=1;i<=(n-6)/7;i++){
cout<<8;
}
cout<<'\n';
}
}
return 0;
}
2[CSP-J 2022] 解密
错因：跟正解相差极大，又是暴力失败的一次,没有找到方程定值(完全平方公式)
正确做法1：
#include<bits/stdc++.h>
using namespace std;
int main(){
//freopen("decode.in","r",stdin);
//freopen("decode.out","w",stdout);
int t;
cin>>t;
while(t--){
long long n,d,e;
cin>>n>>d>>e;
// 根据题面可得 e*d=(p-1)*(q-1)+1=e*d=pq-p-q+2
// 带入n=pq;
//化简得：p+q=n-e*d+2
//完全平方公式：完全平方和-完全平方差
//解得 p-q=sqrt(pow(n-ed+2,2)-4n)
long sum=n-e*d+2;//p+q
long long p=(sqrt(sum*sum-4*n)+sum)/2;
long long q=sum-p;
//前面的表达式中间运算未必准确的整数，所以注意校验
if(p*q==n)cout<<min(p,q)<<" "<<max(p,q)<<'\n';
else cout<<"NO"<<'\n';
}
return 0;
}
正确解法2：
#include<bits/stdc++.h>
using namespace std;
int main(){
int k;
cin>>k;
while(k--){
long long n,d,e;
cin>>n>>d>>e;
//p+q=n-d*e+2//化简所得
long long sumpq=n-d*e+2;
//l,r不为0且p>=q所以sumpq/2>=2q为寻找q值
long long l=1,r=(n-d*e+2)/2;
while(l<r){
int mid=(l+r)/2;
if(mid*(sumpq-mid)>=n){
r=mid;
}else{
l=mid+1;
}
}
if(l*(sumpq-l)==n)cout<<l<<" "<<sumpq-l<<'\n';
else cout<<"NO"<<'\n';
}
return 0;
}
3[CSP-J 2022] 上升点列
错因：。。。(还没做，所以没出错)
正确做法：
#include<bits/stdc++.h>
using namespace std;
int n,k;
struct node{
int x,y;
bool operator <(const node &o)const{
if(x!=o.x){
return x<o.x;
}
return y<o.y;
}
};
node a[100010];
int f[510][110];
//dp[i][j]表示枚举到i时，还可以选j次自由点机会时的最大长度
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
}
sort(a+1,a+1+n);//从小到大枚举边界
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
f[i][k]=1;
for(int s=1;s<i;s++){//枚举前面的点
//题目要求横坐标、纵坐标值均单调不减,不符合要求要跳过
if(a[i].x<a[s].x||a[i].y<a[s].y)continue;
int disx=abs(a[i].x-a[s].x);
int disy=abs(a[i].y-a[s].y);
//两点之间的距离使用曼哈顿距离计算
//但需要减掉两边的交点
int zdis=disx+disy-1;
//需要判断当前联通需要的点数是否<k
if(j+zdis>k)continue;
//f[s][j+zdis]+zdis+1表示第1->i-1;
//第i个结点以内增加zdis个自由点增加距离推到过来
f[i][j]=max(f[i][j],f[s][j+zdis]+zdis+1);
}
}
}
int maxs=0;
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
maxs=max(maxs,f[i][j]+j);
}
}
cout<<maxs;
return 0;
}
4[CSP-J 2023] 旅游巴士
正确做法：
#include<bits/stdc++.h>
using namespace std;
struct node{
int v,w;
};
struct nobe{
int x,cnt;
bool operator < (const nobe& o)const{
return cnt>o.cnt;
}
};
vector<node> c[2000010];
int n,m,k;
bool vis[11000][110];
int ans=0;
int bfs(int u){
priority_queue<nobe> q;
//优先队列可以按照时间排序
q.push({u,0});
while(!q.empty()){
nobe u=q.top();
q.pop();
//题目要求离开时刻为k的倍数，因此要特判
if(u.x==n&&u.cnt%k==0){
return u.cnt;
}
//按时间先访问的元素先vis标记,不然有些先访问到的结点会被后面的vis排除
if(vis[u.x][u.cnt%k])continue;
vis[u.x][u.cnt%k]=1;
for(node s:c[u.x]){
int v=s.v;
//走到当前点的时刻
int nowcnt=u.cnt+1;
//如果这个结点的开放时刻>=走过来的通行时间,则需要增加等待时刻变为k的倍数的时间
if(s.w>=u.cnt+1){
//计算等待时间
int wait=((s.w-nowcnt)/k+1)*k;
nowcnt+=wait;
}
//题目说明了对于每条道路，通行时间为1单位
q.push({v,nowcnt});
}
}
return -1;
}
int main(){
//freopen("bus.in","r",stdin);
//freopen("bus.out","w",stdout);
ios::sync_with_stdio(0);
cin.tie();
cout.tie();
cin>>n>>m>>k;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
c[u].push_back({v,w});
}
cout<<bfs(1);
return 0;
}
5[CSP-S2020] 动物园
思路：开一个check变量记录出现1的位数再去除需要新饲料的位数,除去一定不能为1位，剩下k个位可能为 1，那总动物数就能达到2的k次方，减去已经有的n个动物,所以答案是 pow(2,k)−n。
正确做法：
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long LL;
LL hav=0;
LL a[1000010];
int main(){
//freopen("zoo.in","r",stdin);
//freopen("zoo.ans","w",stdout);
//注意要特判 k=64,n=0的情况,读入量较大,需要写快读
ios::sync_with_stdio(0);
cin.tie();
cout.tie();
int n,m,c,k;
cin>>n>>m>>c>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
hav|=a[i];
}
LL g=0;//记录需要新饲料的动物数量
while(m--){
int p,q;
cin>>p>>q;
//判断 p点是否被覆盖过
if((hav>>p&1)==0){
g|=1ULL<<p;
}
}
LL ans=1;
//总共有2的k次方只动物可以选
//除去一定不能为1的位,剩下t个位可能为1
for(int i=0;i<k;i++){
if((g>>i&1)==0)ans<<=1;
}
ans-=n;
//如果n==0 ,t==64，long long 会溢出
if(ans==0&&n==0){
cout<<"18446744073709551616";
return 0;
}
cout<<ans;
return 0;
}
6[CSP-J 2023] 一元二次方程
注意事项：检查每一个输出格式(肥肠恶心)，p1和p2输出时千万万万万万要小心！！！！！！
思路：按题意模拟即可(太不容易了)，具体步骤看题解，有个约分的方法很好用，具体看题解(标记为$$$)
#include <bits/stdc++.h>
using namespace std;
long long T, M;
long long gcdx(long long a, long long b) {
if (b == 0)
return a;
else
return gcdx(b, a % b);
}
int main() {
ios::sync_with_stdio(0);
cin.tie();
cout.tie();
cin >> T >> M;
while (T--) {
long long a, b, c;
cin >> a >> b >> c;
long long sumabc = b * b - 4 * a * c;
if (sumabc < 0) { //无解
cout << "NO" << '\n';
} else if (sumabc == 0) {
//只有一个解,为(-b)/(2*a)
long long p = -b, q = 2 * a;
long long pq = gcdx(abs(p), abs(q)); //化简
p /= pq, q /= pq;
//$$$可以通过分母和分子同时除以他们的最大公因数化简
//由有理数的定义,存在唯一的两个整数p和q,满足q>0
if (q < 0) {
q = -q, p = -q;
}
//若q=1，则输出{p},否则输出{p}/{q}，其中{n}代表整数n的值；
if (q == 1) {
cout << p << '\n';
} else {
cout << p << "/" << q << '\n';
}
} else {
//否则b*b-4*a*c>0，此时方程有两解
//记其中较大者为x,若x为有理数，则按有理数的格式输x
long long p = -b, q = 2 * a;
long long sqsum = (long long)sqrt(sumabc);
//若 x 为有理数，则按有理数的格式输出 x
if (sqsum * sqsum == sumabc) {
if (q > 0)
p += sqsum;
else
p -= sqsum;
long long pq = gcdx(abs(p), abs(q));
p /= pq, q /= pq;
if (q < 0) {
q = -q, p = -p;
}
if (q == 1) {
cout << p << '\n';
} else {
cout << p << "/" << q << '\n';
}
} else {
//否则根据上文公式,x可以被唯一表示为x=q1+q2+q2*sqrt(r)的形式
long long pq = gcdx(abs(p), abs(q));
p /= pq, q /= pq;
if (q < 0) {
q = -q, p = -p;
}
if (p != 0) {
//若q1!=0,则按有理数的格式输出q1,并再输出一个加号+
if (q == 1) {
cout << p << '+' ;
} else {
cout << p << '/' << q << '+' ;
}
}
q = abs(2 * a);
p = 1;
long long t = 0; //t代表题面中的r
//r 为正整数且 r>1,且不存在正整数d>1使d2|r（即r不应是d*d的倍数）
for (int r = sqsum; r >= 1; r--) {
if (sumabc % (r * r) == 0) {
p *= r;
t = sumabc / (r * r);
break;
}
}
pq = gcdx(abs(p), abs(q));
q /= pq, p /= pq;
if (q < 0) {
q = -q, p = -p;
}
//若q2=1，则输出 sqrt({r})
//否则若q2为整数，则输出 {q2}*sqrt({r})
//否则若 q3=1/q2 为整数，则输出 sqrt({r})/{q3}
//否则可以证明存在唯一整数c,d满足 c,d>1,gcd(c,d)=1且q2=c/d,此时输出{c}*sqrt({r})/{d}
if (p == q) {
cout << sqrt(t) << '\n';
} else if (q == 1) {
cout << p << "*" << "sqrt(" << t << ")" << '\n';
} else if (p == 1) {
cout << "sqrt(" << t << ")" << "/" << q << '\n';
} else {
cout << p << "*sqrt(" << t << ")/" << q << '\n';
}
}
}
}
return 0;
}
7[CSP-J 2024] 接龙
思路 ：
思路直达
#include <bits/stdc++.h>
using namespace std;
vector<int> num[2000010];
//num[i]表示第i个人的整数序列词库
long long dp[105][200005];
//dp[i][j]表示第i轮,最后一个元素恰好为j是否成立
int main() {
ios::sync_with_stdio(0);
cin.tie();
cout.tie();
int T;
cin >> T;
while (T--) {
int n, k, q;
cin >> n >> k >> q;
memset(dp, -1, sizeof(dp));
for (int i = 1; i <= n; i++) {
int l;
cin >> l;
num[i].clear();
//清除上一组的数据
for (int j = 1; j <= l; j++) {
int s;
cin >> s;
num[i].push_back(s);
}
}
dp[0][1] = 0;
//初始化第0轮结尾元素为1的方案数为0
for (int t = 1; t <= 100; t++) { //最多只有100轮
for (int i = 1; i <= n; i++) {
int len = 0;
//冷却计数器(判断第i个人在本轮是否可以接龙)
for (auto x : num[i]) {
len = max(len - 1, 0);
//冷却缩减
if (len > 0) { //第i个人不能接龙时
if (dp[t][x] == -1) {
//如果没有人标记结尾元素为i，就标记
dp[t][x] = i;
} else if (dp[t][x] && dp[t][x] != i) {
//如果有其他人标记，设为冲突状态0
dp[t][x] = 0;
}
}
// 如果前一回合该数字被其他人标记过
if (dp[t - 1][x] != -1 && dp[t - 1][x] != i) {
//重置冷却
len = k;
}
}
}
}
while (q--) {
int r, c;
cin >> r >> c;
//通过查询dp[r][c]来判断是否成立
if (dp[r][c] != -1) {
cout << 1 << '\n';
} else {
cout << 0 << '\n';
}
}
}
return 0;
}
8[CSP-J 2022] 逻辑表达式
#include <bits/stdc++.h>
using namespace std;
const int N =1e6 + 5;
char c[N];
int l1[N], l2[N], c1[N], c2[N];
//l1[i] 代表目前最后一个在i层括号的'|'运算符
//l2[i] 代表目前最后一个在i层括号的'&'运算符
//c1[i] 代表目前和i同层的最后一个'|'运算符
//c2[i] 代表目前和i同层的最后一个'&'运算符
int cnt1 = 0, cnt2 = 0;
//cnt1和cnt2分别计算a&b 和 a|b 的“短路”的次数
int dfs(int l, int r) {
//1|0或者1|1都是'|'短路
if (c1[r] >= l) {
int ans = dfs(l, c1[r] - 1);
if (ans == 1) {
++cnt1;
return 1;
}
return (ans | dfs(c1[r] + 1, r));
}
//0&1或者0&0都是'&'短路
if (c2[r] >= l) {
int ans = dfs(l, c2[r] - 1);
if (ans == 0) {
++cnt2;
return 0;
}
return (ans & dfs(c2[r] + 1, r));
}
////不在括号内的运算符不存在
if (c[l] == '(' && c[r] == ')') {
return dfs(l + 1, r - 1); //去除括号
}
return c[l] - '0';
}
int main () {
ios::sync_with_stdio(0);
cin.tie();
cout.tie();
cin>>c+1;
int x = 0,len=strlen(c + 1);//strlen(c+1)调用超时？x表示当前括号有x层
for (int i = 1; i <= len; i++) {
if (c[i] == '(')
x++;
else if (c[i] == ')')
x--;
else if (c[i] == '|')
l1[x] = i;
else if (c[i] == '&')
l2[x] = i;
//最后一个在i这个位置前且与i同层的'|'运算符
c1[i] = l1[x];
//最后一个在i这个位置前且与i同层的'&'运算符
c2[i] = l2[x];
}
int answer = dfs(1, len);
cout<<answer<<'\n';
cout<<cnt2<<" "<<cnt1;
return 0;
}
C24zhaozicheng
LV 10
@
2025-7-7 19:19:34