xp03_A杭州 永久复习帖
2025-08-15 11:03:00
发布于：浙江
687阅读
0回复
0点赞
报名指导网站
迷宫
细胞
迷路的小猫
联通组件数
充满希望的骑士与棋盘
邻接表存图
奖学金
拓扑排序
连通块问题BFS
#include<bits/stdc++.h>
using namespace std;
int n,m,a[1000010];
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
//第五次出现的编号
//最后第二次出现的编号
//输出整数 q 的数量。
while(m--){
int x;
cin>>x;
int first = lower_bound(a+1,a+1+n,x)-a;//第1个大于等于x的位置
if(first+4<=n && a[first+4]==x)cout<<first+4<<" ";
else cout<<-1<<" ";
int last = upper_bound(a+1,a+1+n,x)-a;//第1个大于x的位置
if(last-2>=1 && a[last-2]==x)cout<<last-2<<" ";
else cout<<-1<<" ";
cout<<last-first<<endl;
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100010];
int get_first(int x){
int l = 1,r = n;
while(l<r){
int mid = l+r>>1;
if(a[mid]>=x)r=mid;
else l=mid+1;
}
return l;
}
int get_last(int x){
int l = 1,r = n;
while(l<r){
int mid = (l+r+1)>>1;
if(a[mid]<=x)l=mid;
else r=mid-1;
}
return l;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
//第五次出现的编号
//最后第二次出现的编号
//输出整数 q 的数量。
while(m--){
int x;
cin>>x;
int first = get_first(x);
int last = get_last(x);
if(first+4<=n && a[first+4]==x)cout<<first+4<<" ";
else cout<<"-1 ";
if(last-1>=1 && a[last-1]==x)cout<<last-1<<" ";
else cout<<"-1 ";
if(a[first]==x)cout<<last-first+1<<endl;
else cout<<0<<endl;
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,p,a[510000],c[510000],ans =0;
int main(){
cin >> n >> p;
for(int i = 1; i <= n; i ++){
cin >> a[i];
c[i] = a[i] - a[i - 1];
}
for(int i = 1; i <= p; i ++){
int x,y,z;
cin >> x >> y >> z;
c[x] += z;
c[y + 1] -= z;
}
ans = 1e9;
for(int i = 1; i <= n; i ++){
c[i] = c[i] + c[i - 1];
ans = min(ans, c[i]);
}
cout << ans;
}
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
// struct pair{
// int first,second;
// };
vector<pair<int,int>> tr[N];//邻接表存图
int n,m;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;//用pair小根堆的排序规则就是pair的first信息
int dist[N];//存储1号点到所有点的距离
bool vis[N];//判断是否已经被更新过的点
int main(){
cin>>n>>m;
while(m--){
int a,b,c;
cin>>a>>b>>c;
tr[a].push_back({b,c});
}
for(int i=1;i<=n;i++)dist[i]=1e9;
dist[1] = 0;
q.push({0,1});
while(q.size()){
auto node = q.top();
int u = node.second;
q.pop();
if(vis[u])continue;
vis[u] = true;
for(auto x:tr[u]){
int ne = x.first,w = x.second;
if(dist[ne]>dist[u]+w){
dist[ne]=dist[u]+w;
q.push({dist[ne],ne});
}
}
}
for(int i=1;i<=n;i++){
if(dist[i]==1e9)cout<<-1<<" ";
else cout<<dist[i]<<" ";
}
return 0;
}
结构体运算符重载
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
struct Node {
int id;
int dist;
bool operator<(const Node& other) const {
return dist > other.dist;
}
};
vector<pair<int, int>> tr[N];
int n, m;
int dist[N];
bool vis[N];
int main() {
cin >> n >> m;
while (m--) {
int a, b, c;
cin >> a >> b >> c;
tr[a].push_back({b, c});
}
for (int i = 1; i <= n; i++) dist[i] = 1e9;
dist[1] = 0;
priority_queue<Node> q;
q.push({1, 0});
while (!q.empty()) {
Node u = q.top();
q.pop();
if (vis[u.id]) continue;
vis[u.id] = true;
for (auto x : tr[u.id]) {
int v = x.first;
int w = x.second;
if (dist[v] > dist[u.id] + w) {
dist[v] = dist[u.id] + w;
q.push({v, dist[v]});
}
}
}
for (int i = 1; i <= n; i++) {
if (dist[i] == 1e9) cout << -1 << " ";
else cout << dist[i] << " ";
}
return 0;
}
最长上升子序列
#include<bits/stdc++.h>
using namespace std;
int n,a[1010];
// 1.创建动态规划数组 dp
// 2.转移方程
// 3.初始化dp数组
// 4.实现
int dp[1010];//前i个数里，以a[i]这个数结尾的最长上升子序列的长度
// (a[i]>a[j]) dp[i] = max((1<=j<i-1) dp[j] + 1)
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
//前i个
for(int i=1;i<=n;i++){
dp[i] = 1;//初始化
for(int j=1;j<=i-1;j++){
if(a[i]>a[j]) dp[i] = max(dp[j] + 1,dp[i]);
}
}
int mx = 0;
for(int i=1;i<=n;i++)mx=max(mx,dp[i]);
cout<<mx;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int a[20];
int n,ans;
vector<int> tr;
void dfs(int u){
if(u==n+1){
bool flag = true;
int sum = 0;
for(int i=0;i<tr.size();i++)sum+=tr[i];
for(int i=1;i<tr.size();i++){
if(tr[i]<=tr[i-1]){
flag = false;
}
}
if(flag){
ans=max(ans,sum);
}
return;
}
tr.push_back(a[u]);
dfs(u+1);
tr.pop_back();
dfs(u+1);
}
int main() {
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
dfs(1);
cout<<ans;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,a[1010];
// 1.创建动态规划数组 dp
// 2.转移方程
// 3.初始化dp数组
// 4.实现
int dp[1010];//前i个数里，以a[i]这个数结尾的上升子序列的最大护甲总和
// dp[i] = a[i];
// (a[i]>a[j]) dp[i] = max((1<=j<i-1) dp[j] + a[i])
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
//前i个
for(int i=1;i<=n;i++){
dp[i] = a[i];//初始化
for(int j=1;j<=i-1;j++){
if(a[i]>a[j]) dp[i] = max(dp[j] + a[i],dp[i]);
}
}
int mx = 0;
for(int i=1;i<=n;i++)mx=max(mx,dp[i]);
cout<<mx;
return 0;
}
二进制枚举
//01DFS枚举 二进制枚举
#include<bits/stdc++.h>
using namespace std;
bool isprime(int x){
if(x<2)return false;
for(int i=2;i*i<=x;i++){
if(x%i==0)return false;
}
return true;
}
int a[20];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)cin>>a[i];
int ans = 0;
for(int i=0;i<1<<n;i++){// 000 - 111
int sum = 0;
for(int j=0;j<n;j++){
if((i>>j)&1)sum+=a[j];//判断二进制的每一个是否是1
}
if(isprime(sum))ans++;
}
cout<<ans;
return 0;
}
魔法契约
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("aaa.in","r",stdin);
freopen("aaa.out","w",stdout);
int n;
cin>>n;
int w[n+1],r[n+1];
for(int i=1;i<=n;i++){
cin>>r[i]>>w[i];
}
bool flag = true;
for(int i=1;i<=n-1;i++)if(w[i]>=233)flag = false;
for(int i=2;i<=n;i++)if(r[i]<r[i-1] || w[i]<w[i-1])flag = false;
if(flag)cout<<"YES";
else cout<<"NO";
fclose(stdin);
fclose(stdout);
return 0;
}
加密
// s : 10101
// s' : 11111
// s'': 10000
// s1' = s1 s2' = s2^s1
#include<bits/stdc++.h>
using namespace std;
int a[100010],b[100010];
int main(){
freopen("bbb.in","r",stdin);
freopen("bbb.out","w",stdout);
int n,t;
cin>>n>>t;
string s;
cin>>s;
for(int i=1;i<=n;i++)a[i] = s[i-1]-48;
while(t--){
for(int i=0;i<=n;i++)b[i] = a[i];
for(int i=1;i<=n;i++)a[i]=b[i]^b[i-1];
}
for(int i=1;i<=n;i++)cout<<a[i];
fclose(stdin);
fclose(stdout);
return 0;
}
// s : 10101
// s' : 11111
// s'': 10000
// s1' = s1 s2' = s2^s1
#include<bits/stdc++.h>
using namespace std;
int a[100010];
int main(){
freopen("bbb.in","r",stdin);
freopen("bbb.out","w",stdout);
int n,t;
cin>>n>>t;
string s;
cin>>s;
for(int i=1;i<=n;i++)a[i] = s[i-1]-48;
while(t--){
for(int i=n;i>=1;i--)a[i]=a[i]^a[i-1];
}
for(int i=1;i<=n;i++)cout<<a[i];
fclose(stdin);
fclose(stdout);
return 0;
}
魔法日
#include<bits/stdc++.h>
using namespace std;
long long a[10010],tot;
//计算0年0月0日 - y年m月d日
long long day(int y,int m,int d){
long long sum = 0;
for(int i=0;i<=y-1;i++){
sum+=tot;
if(i%4==0)sum++;
}
for(int i=1;i<=m-1;i++)sum+=a[i];
sum+=d;
return sum;
}
int main(){
freopen("ccc.in","r",stdin);
freopen("ccc.out","w",stdout);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
tot = 0;
for(int i=1;i<=n;i++){
cin>>a[i];
tot+=a[i];
}
int yb,mb,db,yc,mc,dc;
cin>>yb>>mb>>db>>yc>>mc>>dc;
long long ans = day(yc,mc,dc) - day(yb,mb,db) + 1;
cout<<ans<<endl;
}
fclose(stdin);
fclose(stdout);
return 0;
}
宿命印记
#include<bits/stdc++.h>
using namespace std;
long long t,n,a[10010],b[10010];
int main(){
freopen("ddd.in","r",stdin);
freopen("ddd.out","w",stdout);
cin>>t;
for(int j=1;j<=t;j++){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);//攻击力从小到大排序
b[0]=0;
for(int i=1;i<=n;i++){
b[i]=b[i-1]+a[i];
}
long long ans=0;
for(int i=1;i<=n;i++){
long long x2=i*1000-b[i];
long long y2=b[n]-b[i];
ans=max(ans,x2*y2);
}
cout<<ans<<"\n";
}
fclose(stdin);
fclose(stdout);
return 0;
}
坤坤爱喝可乐
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin>>n;
int ans=n;
int sum=n;
while (sum>=3) {
int num=sum/3;//兑换的可乐
ans+=num; //累加喝的可乐
sum=num+sum%3;//
}
cout<<ans;
}
贪婪的哥布林
// 01背包动态规划
// 1.创建动态规划数组 dp[i][j] = ?
// 从前i个物品中选 并且此时背包容量为j的情况下的最大价值。
// 2.转移方程
// 选 / 不选 体积变，价值变
// 不选 体积不变，价值不变
// dp[i][j] = dp[i-1][j]
// dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]] + v[i])
#include<bits/stdc++.h>
using namespace std;
int w[1010],v[1010];
int dp[1010][1010];
int main(){
int n,V;
cin>>n>>V;
for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
for(int i=1;i<=n;i++){
for(int j=0;j<=V;j++){
dp[i][j] = dp[i-1][j];//不选
if(j>=w[i])dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
}
}
cout<<dp[n][V];
return 0;
}
// 01背包动态规划
// 1.创建动态规划数组 dp[i][j] = ?
// 从前i个物品中选 并且此时背包容量为j的情况下的最大价值。
// 2.转移方程
// 选 / 不选 体积变，价值变
// 不选 体积不变，价值不变
// dp[i][j] = dp[i-1][j]
// dp[i][j] = max(dp[i][j],dp[i-1][j-w[i]] + v[i])
#include<bits/stdc++.h>
using namespace std;
int w[1010],v[1010];
int dp[1010];
int main(){
int n,V;
cin>>n>>V;
for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
for(int i=1;i<=n;i++){
for(int j=V;j>=w[i];j--){
dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[V];
return 0;
}
// 分别表示小智拥有的精灵球数量、皮卡丘的初始体力值，以及野生小精灵的数量。
// 精灵球数量,受到的伤害
// dp[i][j][k] = ?
// //从前i个精灵中抓，并且此时精灵球数量是j，并且皮卡丘体力是k的情况下的最大的精灵的抓取数量
// //选/不选
// dp[i][j][k] = dp[i-1][j][k]
// dp[i][j][k] = dp[i-1][j-a][k-b] + 1;
#include<bits/stdc++.h>
using namespace std;
int w[1010],v[1010];//w 精灵球消耗 v 体力消耗
int dp[2][1001][501];
int main(){
int n,m,k;
cin>>n>>m>>k;
for(int i=1;i<=k;i++)cin>>w[i]>>v[i];
int sum = 0,hp = 0;
for(int i=1;i<=k;i++){
for(int j=0;j<=n;j++){
for(int t=0;t<=m-1;t++){
dp[i&1][j][t] = dp[i-1&1][j][t];
if(j-w[i]>=0 && t-v[i]>=0)dp[i&1][j][t] = max(dp[i&1][j][t],dp[i-1&1][j-w[i]][t-v[i]]+1);
if(sum<dp[i&1][j][t]){
sum = dp[i&1][j][t];
hp = m - t;
}else if(sum==dp[i&1][j][t]){
hp = max(hp,m-t);
}
}
}
}
cout<<sum<<" "<<hp;
return 0;
}
小苹果 90分
#include<bits/stdc++.h>
using namespace std;
bool vis[1000001];
int main(){
freopen("apple.in","r",stdin);
freopen("apple.out","w",stdout);
int n;
cin>>n;
int day = 0,ans = 0,cnt = n;//剩下的苹果
while(cnt){
day++;
int id = 0;
for(int i=1;i<=n;i++){
if(vis[i])continue;
id++;
//当前苹果编号 %3 == 1 , 可以拿走的.
if(id%3==1){
if(i==n) ans = day;//最后一个苹果在第day天被拿走
vis[i] = true;
cnt--;
}
}
}
cout<<day<<" "<<ans;
fclose(stdin);
fclose(stdout);
}
小苹果正解
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("apple.in","r",stdin);
freopen("apple.out","w",stdout);
int n;
cin>>n;//剩下的苹果
int day = 0,ans = 0;
while(n){
day++;//天数+1
if(n%3==1){//如果苹果数量%3==1 说明最后一个苹果会被拿走
if(ans==0)ans = day;//防止答案被覆盖
}
n -= ceil(1.0*n/3);//每一天拿走的苹果是 (n/3)向上取整
}
cout<<day<<" "<<ans;
fclose(stdin);
fclose(stdout);
}
公路
#include <bits/stdc++.h>
using namespace std;
long long v[100005],a[100005],n,d;
// int 4字节 long long 8字节
int main(){
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
cin >> n >> d;//车站数量，一升油能跑 d 公里
for(int i=1;i<=n-1;i++)cin>>v[i];
for(int i=1;i<=n;i++)cin>>a[i];
long long money = 0;
long long sum = 0;
long long dist = 0;//实际的距离
long long mn = 1e9;
for(int i=1;i<=n-1;i++){
sum+=v[i];
mn = min(mn,a[i]);
long long oil = ceil(1.0*(sum-dist)/d);
if(oil<0)oil = 0;
money += oil * mn;
dist += oil * d;
}
cout<<money;
fclose(stdin);
fclose(stdout);
return 0;
}
环球旅行
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
int y,w;
};
vector<node> g[100010];
int d[100010];//从起点到达其他所有点的距离
int main(){
cin>>n>>m;
while(m--){
int a,b,c;
cin>>a>>b>>c;
g[a].push_back({b,c});
}
for(int i=1;i<=n;i++)d[i]=1e9;
queue<int> q;
q.push(1);
d[1] = 1;
while(q.size()){
int u = q.front();
q.pop();
for(int i=0;i<g[u].size();i++){
node now = g[u][i];
int ne = now.y,time = now.w;
int mx = max(d[u]+1,time+1);
if(d[ne] > mx){
d[ne] = mx;
q.push(ne);
}
}
}
cout<<d[n];
return 0;
}
环球旅行 dijkstra
#include<bits/stdc++.h>
using namespace std;
int n,m;
struct node{
int y,w;
};
vector<node> g[100010];
int d[100010];//从起点到达其他所有点的距离
bool vis[100010];
int main(){
cin>>n>>m;
while(m--){
int a,b,c;
cin>>a>>b>>c;
g[a].push_back({b,c});
}
for(int i=1;i<=n;i++)d[i]=1e9;
priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>> q;
q.push({1,1});
d[1] = 1;
while(q.size()){
auto cur = q.top();
int u = cur.second;
q.pop();
if(vis[u])continue;
vis[u]=true;
for(int i=0;i<g[u].size();i++){
node now = g[u][i];
int ne = now.y,time = now.w;//ne相邻点 time u->ne
int mx = max(d[u]+1,time+1);
if(d[ne] > mx){
d[ne] = mx;
q.push({d[ne],ne});
}
}
}
cout<<d[n];
return 0;
}
旅游巴士 35分 djkstra + 动态规划
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
struct node{
int y,w;
};
vector<node> g[10010];
int d[10010][110];//从起点到达i点的距离%k==j 的情况下的最短距离
bool vis[10010][110];
int main(){
freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
cin>>n>>m>>k;
while(m--){
int a,b,c;
cin>>a>>b>>c;
g[a].push_back({b,c});
}
for(int i=1;i<=n;i++)
for(int j=0;j<=k-1;j++)
d[i][j]=1e9;
priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>> q;
q.push({0,1});
d[1][0] = 0;//到达1点的 并且当前距离%k余数为0的情况下的最短路径
while(q.size()){
auto cur = q.top();
int u = cur.second,dist = cur.first;
q.pop();
if(vis[u][dist%k])continue;
vis[u][dist%k]=true;
for(int i=0;i<g[u].size();i++){
node now = g[u][i];
int ne = now.y,time = now.w;//ne相邻点 time u->ne
if(d[ne][(dist+1)%k] > d[u][dist%k] + 1){
d[ne][(dist+1)%k] = d[u][dist%k] + 1;
q.push({d[ne][(dist+1)%k],ne});
}
}
}
if(d[n][0]==1e9)cout<<-1;
else cout<<d[n][0];
fclose(stdin);
fclose(stdout);
return 0;
}
旅游巴士 25分 BFS+换位思考
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
struct node{
int y,w;
};
vector<node> g[100010];
int d[100010];//从起点到达其他所有点的距离
bool vis[100010];
int main(){
freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
cin>>n>>m>>k;
while(m--){
int a,b,c;
cin>>a>>b>>c;
g[a].push_back({b,c});
}
for(int i=1;i<=n;i++)d[i]=1e9;
priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>> q;
q.push({0,1});
d[1] = 0;
while(q.size()){
auto cur = q.top();
int u = cur.second;
q.pop();
if(vis[u])continue;
vis[u]=true;
for(int i=0;i<g[u].size();i++){
node now = g[u][i];
int ne = now.y,time = now.w;//ne相邻点 time u->ne
int mx = max(d[u]+1,time+1);
if(d[ne] > mx){
d[ne] = mx;
q.push({d[ne],ne});
}
}
}
if(d[n]==1e9)cout<<-1;
else cout<<d[n];
fclose(stdin);
fclose(stdout);
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int n,m,k;
struct node{
int y,w;
};
vector<node> g[10010];
int d[10010][110];//从起点到达i点的距离%k==j 的情况下的最短距离
bool vis[10010][110];
int main(){
freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
cin>>n>>m>>k;
while(m--){
int a,b,c;
cin>>a>>b>>c;
g[a].push_back({b,c});
}
for(int i=1;i<=n;i++)
for(int j=0;j<=k-1;j++)
d[i][j]=1e9;
priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>> q;
q.push({0,1});
d[1][0] = 0;//到达1点的 并且当前距离%k余数为0的情况下的最短路径
while(q.size()){
auto cur = q.top();
int u = cur.second,dist = cur.first;
q.pop();
if(vis[u][dist%k])continue;
vis[u][dist%k]=true;
for(int i=0;i<g[u].size();i++){
node now = g[u][i];
int ne = now.y,time = now.w;//ne相邻点 time u->ne
int sum = 0;
if(dist<time){
sum = dist + ceil(1.0*(time-dist)/k)*k + 1;
}else sum = dist + 1;
if(d[ne][sum%k] > sum){
d[ne][sum%k] = sum;
q.push({d[ne][sum%k],ne});
}
}
}
if(d[n][0]==1e9)cout<<-1;
else cout<<d[n][0];
fclose(stdin);
fclose(stdout);
return 0;
}
2022乘方
#include <bits/stdc++.h>
using namespace std;
int main(){
freopen("pow.in" , "r" , stdin);
freopen("pow.out" , "w" , stdout);
// a = 1 b = 1e9
int a,b;
cin>>a>>b;
if(a==1){
cout<<1;
return 0;
}
int ans = 1;
for(int i=1;i<=b;i++){
if(ans>1e9/a){
cout<<-1;
return 0;
}
ans*=a;
}
cout<<ans;
fclose(stdin);
fclose(stdout);
return 0;
}
pow做法
#include<bits/stdc++.h>
using namespace std;
int main(){
freopen("pow.in","r",stdin);
freopen("pow.out","w",stdout);
long long a,b;
cin>>a>>b;
long long ans=0;
ans=pow(a,b);
if(ans>1e9||ans<=0) cout<<-1;
else cout<<ans;
fclose(stdin);
fclose(stdout);
}
解密 60分
#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--){
int n,d,e;
cin>>n>>d>>e;
// n = p*q p,q都是n的约数
int ansp = 0,ansq = 0;
for(int p=1;p*p<=n;p++){
if(n%p==0){
int q = n/p;
if(e*d == (p-1)*(q-1) + 1){
ansp = p;
ansq = q;
}
}
}
if(ansp*ansq!=n)cout<<"NO"<<endl;
else cout<<ansp<<" "<<ansq<<endl;
}
fclose(stdin);
fclose(stdout);
}
解密
#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;
long long t1 = n;//p*q;
long long t2 = n-e*d+2;//p+q
long long ans = t2*t2 - 4*t1; //(p+q)^2 - 4pq = (p-q)^2
long long sum = sqrt(ans);//p-q
if(sum*sum==ans){
long long p = (t2+sum)/2;
long long q = n/p;
if(p>q)swap(p,q);
cout<<p<<" "<<q<<endl;
}else{
cout<<"NO"<<endl;
}
}
fclose(stdin);
fclose(stdout);
}
解密 二分做法
#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;
long long sum = n-e*d+2;// p+q = sum
long long l = 1,r = sum/2;
while(l<r){
long long mid = l+r>>1;
long long p = mid , q = sum - p;
if(p*q>=n)r=mid;
else l=mid+1;
}
long long p = l,q = sum - p;
if(p*q==n){
if(p>q)swap(p,q);
cout<<p<<" "<<q<<endl;
}else{
cout<<"NO"<<endl;
}
}
fclose(stdin);
fclose(stdout);
}
上升点列(撤所管理员做法)
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y;
}a[510];
int n,k;
bool cmp(node a,node b){
if(a.x!=b.x)return a.x<b.x;
return a.y<b.y;
}
vector<node> tr;
int ans = 0;
void dfs(int u){
if(u==n+1){
bool ju = true;
int len = tr.size();
for(int i=1;i<tr.size();i++){
node cur = tr[i],pre = tr[i-1];
//欧几里得距离是否为1
if(tr[i].x-tr[i-1].x+tr[i].y-tr[i-1].y!=1){
ju=false;
}
}
if(ju){
ans=max(ans,len);
}
return;
}
tr.push_back(a[u]);
dfs(u+1);
tr.pop_back();
dfs(u+1);
}
int main(){
freopen("point.in","r",stdin);
freopen("point.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
}
sort(a+1,a+n+1,cmp);
dfs(1);
cout<<ans;
fclose(stdin);
fclose(stdout);
return 0;
}
最长上升子序列
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y;
}a[510];
int n,k;
bool cmp(node a,node b){
if(a.x!=b.x)return a.x<b.x;
return a.y<b.y;
}
int dp[510];//从前i个坐标中选，以(x,y)坐标结尾的最长上升子序列的长度
// dp[i] = (a[i].y>=a[j].y) (ojld == 1) dp[j] + 1
int main(){
freopen("point.in","r",stdin);
freopen("point.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
}
sort(a+1,a+n+1,cmp);
int mx = 0;
for(int i=1;i<=n;i++){
dp[i] = 1;
for(int j=1;j<=i-1;j++){
if(a[i].x-a[j].x+abs(a[i].y-a[j].y)==1){
dp[i] = max(dp[j]+1,dp[i]);
}
}
mx = max(mx,dp[i]);
}
cout<<mx;
fclose(stdin);
fclose(stdout);
return 0;
}
01背包+最长上升子序列
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y;
}a[510];
int n,k;
bool cmp(node a,node b){
if(a.x!=b.x)return a.x<b.x;
return a.y<b.y;
}
int dp[510][110];
//从前i个坐标中选，以(x,y)坐标结尾，并且此时花了j个桥梁的最长上升子序列的长度
// dp[i][j] = (k-i ojld <= j-1) dp[j] + sum + 1
int main(){
freopen("point.in","r",stdin);
freopen("point.out","w",stdout);
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
}
sort(a+1,a+n+1,cmp);
int mx = 0;
for(int i=1;i<=n;i++){
dp[i][0] = 1;
for(int j=0;j<=k;j++){
for(int t = 1;t <= i-1;t++){
if(a[i].y>=a[t].y){
int ojld = (abs(a[i].x-a[t].x)+abs(a[i].y-a[t].y))-1;//需要的桥梁数量
if(j>=ojld)dp[i][j] = max(dp[i][j],dp[t][j-ojld]+ojld+1);
}
}
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<=k;j++){
mx = max(mx,dp[i][j]+k-j);
}
}
cout<<mx;
fclose(stdin);
fclose(stdout);
return 0;
}
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <stack>
using namespace std;
struct Data{
bool f;
int conflict1, conflict2;
}data;
stack<Data > num;
stack<char > op;
void eval(){
auto b = num.top(); num.pop();
auto a = num.top(); num.pop();
auto c = op.top(); op.pop();
Data x;
if(c == '&'){
if(!a.f){
x.f = 0;
x.conflict1 = a.conflict1 + 1;
x.conflict2 = a.conflict2;
}
else{
x.f = a.f & b.f;
x.conflict1 = a.conflict1 + b.conflict1;
x.conflict2 = a.conflict2 + b.conflict2;
}
}
else{
if(a.f){
x.f = 1;
x.conflict1 = a.conflict1;
x.conflict2 = a.conflict2 + 1;
}
else{
x.f = a.f | b.f;
x.conflict1 = a.conflict1 + b.conflict1;
x.conflict2 = a.conflict2 + b.conflict2;
}
}
num.push(x);
}
int main(){
freopen("expr.in","r",stdin);
freopen("expr.out","w",stdout);
string s;
cin >> s;
unordered_map<char , int > pr{{'|', 1}, {'&', 2}};
for(int i = 0; i < s.size(); i ++ ){
auto c = s[i];
if(isdigit(c)){
Data temp;
temp.f = c - '0';
temp.conflict1 = temp.conflict2 = 0;
num.push(temp);
}
else if(c == '('){
op.push(c);
}
else if(c == ')'){
while(op.top() != '('){
eval();
}
op.pop();
}
else{
while(op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
op.push(c);
}
}
while(op.size()) eval();
cout << num.top().f << endl;
cout << num.top().conflict1 << " " << num.top().conflict2 << endl;
fclose(stdin);
fclose(stdout);
return 0;
}
地图探险
#include<bits/stdc++.h>
using namespace std;
char a[1105][1105];
bool vis[1100][1100];
//0 右 1 下 2 左 3 上
int dx[] = {0,1,0,-1};
int dy[] = {1,0,-1,0};
int main(){
freopen("explore.in", "r", stdin);
freopen("explore.out", "w", stdout);
int t;
cin>>t;
while(t--){
int n,m,k,x,y,d;
cin>>n>>m>>k>>x>>y>>d;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
vis[i][j] = 0;
}
}
vis[x][y] = 1;//机器人出生点
while(k--){
//往d这个方向走一格
int nx = x + dx[d];
int ny = y + dy[d];
//如果可以走
if(nx>=1 && nx<=n && ny>=1 && ny<=m && a[nx][ny]!='x'){
x = nx;
y = ny;
vis[x][y] = 1;//当前点被走到了
}else{
d = (d+1)%4;//否则越界或者碰到障碍物了，方向扭转一下
}
}
int ans = 0;
//统计走过多少个格子
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(vis[i][j])ans++;
}
}
cout<<ans<<endl;
}
fclose(stdin);
fclose(stdout);
}
五子棋
#include <iostream>
#include <vector>
using namespace std;
const int dir[8][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, -1}, {-1, 1}, {1, 1}, {-1, -1}};
int mod(int x, int m) {
return (x % m + m) % m;
}
int main() {
int n, m, t;
cin >> n >> m >> t;
t += 1;
vector<vector<int>> g(n, vector<int>(m));
vector<vector<int>> back_up(n, vector<int>(m));
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < m; j++) {
back_up[i][j] = g[i][j] = s[j] - '0';
}
}
while (t-- > 0) {
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
g[i][j] = back_up[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int a[4] = {1, 1, 1, 1};
for (int k = 0; k <= 4; k++) {
if (g[mod(i + k, n)][j] == 0) {
a[0] = 0;
break;
}
}
for (int k = 0; k <= 4; k++) {
if (g[i][mod(j + k, m)] == 0) {
a[1] = 0;
break;
}
}
for (int k = 0; k <= 4; k++) {
if (g[mod(i + k, n)][mod(j + k, m)] == 0) {
a[2] = 0;
break;
}
}
for (int k = 0; k <= 4; k++) {
if (g[mod(i - k, n)][mod(j + k, m)] == 0) {
a[3] = 0;
break;
}
}
for (int k = 0; k < 4; k++) {
ans += a[k];
}
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int cnt = 0;
for (int k = 0; k < 8; k++) {
int ni = mod(i + dir[k][0], n);
int nj = mod(j + dir[k][1], m);
if (g[ni][nj] == 1) cnt++;
}
if (g[i][j] == 1) {
if (cnt < 2) back_up[i][j] = 0;
else if (cnt <= 3) back_up[i][j] = 1;
else back_up[i][j] = 0;
} else {
if (cnt == 3) back_up[i][j] = 1;
}
}
}
cout << ans << "\n";
}
return 0;
}
小木棍
#include<bits/stdc++.h>
using namespace std;
int ans[10] = {6,2,5,5,4,5,6,3,7,6};
long long n,res = 1e18;
// 3*10 + 5
void dfs(int u,long long sum,long long wood){
if(sum>res)return;
if(wood>n)return;
if(wood==n){
res=min(res,sum);
return;
}
for(int i=(u==1?1:0);i<=9;i++){
dfs(u+1,sum*10+i,wood+ans[i]);
}
}
int main() {
for(int i=1;i<=100;i++){
res=1e18;
n = i;
dfs(1,0,0);
cout<<i<<" "<<res<<endl;
}
return 0;
}
栩栩如死
有帮助，赞一个