1001：
输出A&B 特判A&B=0
1007:
思路：按照题意去写，分为四个部分，只有第三部分与第一部分相反，其余都与第一部分相同
所以我们以第一部分为基准，去扩展另三部分，从部分到整体
#include<bits/stdc++.h> #define ll long long using namespace std; ll h,t,n,m[1100][1100]; int main() {cin>>t;while(t--){cin>>n;h = 2;m[1][1] = 1;m[1][2] = 1;m[2][1] = 0;m[2][2] = 1;while(--n)//从部分扩展到整体 {for(int i = 1;i<=h;i++) //第二块的值与第一块相同 for(int j = 1+h;j<=2*h;j++)m[i][j] = m[i][j-h];for(int i = h+1;i<=h*2;i++) //第三块的值与第一块相同 for(int j = 1+h;j<=2*h;j++)m[i][j] = m[i-h][j-h];for(int i = h+1;i<=h*2;i++) //第四块的值与第一块相反 for(int j = 1;j<=h;j++)if(m[i-h][j]) m[i][j] = 0;elsem[i][j] = 1;h*=2;}for(int i = 1;i<=h;i++){for(int j = 1;j<=h;j++){if(m[i][j]==1)cout<<'C';elsecout<<'P';}cout<<endl;}}return 0; }
1006 ---模拟栈
#include<bits/stdc++.h> using namespace std; #define maxn 100010 int a[maxn]; int vis[maxn]; int main() {int n,m,x;cin>>n>>m;stack<int>t;for(int i=0;i<n;i++)cin>>a[i];for(int i=0;i<n;i++)t.push(a[n-i-1]);for(int i=0;i<m;i++){cin>>x;t.push(x);}memset(vis,0,sizeof(vis));while(!t.empty()){int x=t.top();if(vis[x]==0){cout<<x<<" ";vis[x]=1;}t.pop();} }
1008：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=100010; int a[maxn],n,k,b[maxn],nn; ll ans,cnt,res,ans2; bool cmp(int a,int b) {return a>b; } int main() {int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&k);ans=k;res=ans2=0;cnt=1;nn=n;for(int i=1;i<=n;i++){scanf("%d",&a[i]);cnt+=a[i]/k;ans=ans+a[i];b[i]=a[i]%k;}sort(b+1,b+n+1,cmp);if(cnt>=n) printf("%lld\n",ans);else{int cnt2=n-cnt;//没在煮的时间里抓鱼的数目int t=0; for(int i=1;i<=n;i++){t++;ans+=k-b[i];if(t==cnt2)break;}printf("%lld\n",ans);}} }
1004:path
解法：我们对于所有点u，对它的出边按照边权排序，然后用一个set维护当前优先队列存了的所有路径长度，但是只维护max(k)个元素，我们把所有边存进优先队列，每次出队，我们枚举当前节点的所有出边，如果set元素数量低于max(k)或者当前路径长度+当前出边小于set最大的元素，那么我们就把新的路径长度更新到set并且存进优先队列，否则中断枚举，直到优先队列出队max(k)次即可.
#include<bits/stdc++.h> #define pi pair<int, int> #define mk make_pair #define ll long long using namespace std; const int maxn = 5e4 + 10; struct node {int u;ll dis;bool operator<(const node& t) const {return dis > t.dis;} };vector<pi> G[maxn];//存G[u]=mk{w,v}; 存点的出边 ---作用是建图 priority_queue<node> q;//路径的优先队列 u,dis multiset<ll> s;//存路径长度的可重复集合---作用是帮助构建优先队列 ll ans[maxn * 10];//存询问的路径长度答案 int qry[maxn];//存询问 void init(int n) {s.clear();for (int i = 1; i <= n; i++)G[i].clear();while (!q.empty())q.pop(); } int main() {int T;scanf("%d", &T);while (T--) {int n, m, Q, u, v, w, k, mx = 0;scanf("%d%d%d", &n, &m, &Q);for (int i = 1; i <= m; i++) {scanf("%d%d%d", &u, &v, &w);G[u].push_back(mk(w, v));//存图 q.push(node{v, w});//存路径---都存是因为我们求的是所有可能路径，不存在固定的起点和终点 s.insert(w);//存路径长度 }for (int i = 1; i <= n; i++)//对每个起始点，根据起始点到终点的距离w(这个是make_pair的第一个元素)进行排序 sort(G[i].begin(), G[i].end());for (int i = 1; i <= Q; i++)//存要询问的第Q条路径 scanf("%d", &qry[i]), mx = max(mx, qry[i]);//记录要询问的最大路径数 int cnt = 0;while (cnt <= mx) {node tmp = q.top();q.pop();ans[++cnt] = tmp.dis; if (cnt >= mx)break;u = tmp.u;//起点 for (auto it :G[u]) //遍历一个容器 {//只有两种情况需要更新set并且存进优先队列v = it.second; //---遍历u的出边 ll w = it.first + tmp.dis; if (s.size() >= mx) {//当前路径长度+当前出边小于set最大的元素auto cat = --s.end();//set的最大元素--最大路径长度 if (w >= *cat)//当前路径长度+当前出边 > set最大的元素break;s.erase(cat);//当前路径长度+当前出边 < set最大的元素----更新set s.insert(w);}else//set元素数量低于max(k) s.insert(w);node now;now.dis=w,now.u=v; q.push(now);}}for (int i = 1; i <= Q; i++)printf("%lld\n", ans[qry[i]]);init(n);} }
#include<bits/stdc++.h> #define mk make_pair #define pi pair<int,int> #define ll long long #define maxn 50010 using namespace std; struct node{int u,dis;bool operator<(const node& t)const{return dis>t.dis;} }; vector<pi> G[maxn]; multiset<ll> s; ll ans[maxn]; priority_queue<node> q; int qry[maxn]; void Init(int n) {s.clear();for(int i=1;i<=n;i++)G[i].clear();while(!q.empty())q.pop(); } int main() {int t,n,m,Q,u,v,w,mx;scanf("%d",&t);while(t--){scanf("%d%d%d",&n,&m,&Q);for(int i=0;i<m;i++){scanf("%d%d%d",&u,&v,&w);s.insert(w);G[u].push_back(mk(w,v));q.push(node{v,w});}for (int i = 1; i <= n; i++)//对每个起始点，根据起始点到终点的距离w(这个是make_pair的第一个元素)进行排序 sort(G[i].begin(), G[i].end());mx=0;for(int i=0;i<Q;i++){scanf("%d",&qry[i]);mx=max(mx,qry[i]);}int cnt=0;while(cnt<=mx){node tmp=q.top();q.pop();cnt++;ans[cnt]=tmp.dis;u=tmp.u;for(auto it:G[u]){v=it.second;ll w=it.first+tmp.dis;if(s.size()>=mx){auto cat=--s.end();if(w>*cat)break;s.erase(cat);s.insert(w);}elses.insert(w);node now;now.dis=w,now.u=v; q.push(now);}}for(int i=0;i<Q;i++)printf("%lld\n",ans[qry[i]]);Init(n);} }
参考博客：https://blog.csdn.net/ccsu_cat/article/details/100047649