状态奇差，只写了4题
Problem A
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 262144/262144K (Java/Other)
Problem Description
WNJXYK and VineAsh are friends. They often play puzzle games together.
One day, WNJXYK found a very interesting puzzle game. At the beginning of this game, he had infinite pattern puzzles, all of which are exactly the same and each pattern puzzle could be considered as a number sequence P1,P2,…Pn. Meanwhile, he had another number sequence T1,T2,…,Tm which is his target. During this game, he could pick up a pattern puzzle and delete some numbers in it (Or don't delete any number at all) in order to build a processed puzzle. His goal is to build some processed puzzles and concatenate them together to construct his target.
This game is so easy. To show off in front of VineAsh, WNJXYK wanted to do something harder. He decided to use minimum number of pattern puzzles to construct the target. Soon after, he realized that even though he found a solution he could not prove that the solution uses minimum number of pattern puzzles.
Therefore, WNJXYK wants you to tell him the minimum number of pattern puzzles he needs to use in order to construct the target.
Input
There are multiple test causes.
The first line of input contains an integer T, representing the number of test cases.
For each test case, the first line contains two integers n, m, indicating the length of pattern puzzle and the length of target. The second line contains a sequence with n integers P1,P2,…,Pn which is the pattern puzzle. The third line contains a sequence with m integers T1,T2,…,Tn which is the target.
Output
For each test case, output the answer which is the minimum number of pattern puzzles WNJXKY needs to use in a line.
I11 addition, if WNJXKY could not construct the target with pattern puzzles, please output −1.
Sample Input
3 3 5 11 22 33 11 22 33 11 22 3 6 1 2 3 3 2 1 3 2 1 5 5 1 2 3 4 5 1 2 3 4 6
Sample Output
2 5 -1
Hint
1 ≤ T ≤ 10
1 ≤ n, m ≤ 1e5
1 ≤ Pi, Ti ≤ 1e9
For the second sample, "3"+"2"+"1 3"+"2"+"1"="3 2 1 3 2 1"
乱搞
#include<bits/stdc++.h>
using namespace std;
#define rep(i,tot,b) for(int i=(tot);i<=(b);++i)
#define dep(i,tot,b) for(int i=(tot);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
int a[maxn],b[maxn],tot[maxn<<1],n,m,Index;
int pre[maxn<<1],last[maxn<<1],pos[maxn<<1],cnt[maxn<<1];
map<int,int>s1,s2;
void init(){rep(i,1,maxn-10) pre[i]=last[i]=pos[i]=maxn,cnt[i]=Index=0;}
void readin(){
scanf("%d%d",&n,&m);
rep(i,1,n) scanf("%d",&a[i]),tot[++Index]=a[i];
rep(i,1,m) scanf("%d",&b[i]),tot[++Index]=b[i];
}
int ls(){
sort(tot+1,tot+1+Index);
int SZ=unique(tot+1,tot+1+Index)-tot-1;
rep(i,1,n) a[i]=lower_bound(tot+1,tot+1+SZ,a[i])-tot,cnt[a[i]]=1;
rep(i,1,m){
b[i]=lower_bound(tot+1,tot+1+SZ,b[i])-tot;
if(!cnt[b[i]]) return 0;
}
return 1;
}
void solve(){
init();
readin();
if(!ls()) {printf("-1\n");return;}
rep(i,1,n) pre[a[i]]=min(pre[a[i]],i);
dep(i,n,1) last[i]=pos[a[i]],pos[a[i]]=i;
int pos1=1,pos2=pre[b[pos1]],ans=0;
while(pos1<=m){
if(pos1==m){ans++;break;}
if(pre[b[pos1+1]]>pos2) pos2=pre[b[pos1+1]],pos1++;
else{
int now=pre[b[pos1+1]];
while(last[now]!=maxn&&last[now]<pos2) now=last[now];
if(last[now]==maxn){pos1++;pos2=pre[b[pos1]];ans++;}
else pos2=last[now],pos1++;
}
}
printf("%d\n",ans);
}
int main(){
int b;cin>>b;
while(b--) solve();
}
Problem B
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 262144/262144K (Java/Other)
Problem Description
WNJIXYK and VineAsh are friends. They both like binary strings very much.
One day, WNJXYK found n binary strings which are in length of k. He should be the happiest person in the world because of owning so many binary strings. But,sadly, he thought that all the binary strings he had are not beautiful.
VineAsh can use a special magic to reverse one digit in one binary siring and she made WNJXYK a promise that she would use her magic to build a beautiful string (which should also be in length of k) based on one binary string WNJXYK had. But she didn't know which string is beautiful in WNJXYK's opinion.
Therefore, VineAsh wants to you tell her the minimum times she should perform her magic if she choose the string optimally and perform her magic on it optimally in the worst situation.
Input
There are multiple test cases.
The first line of input contains a number T, representing the number of test cases.
For each test case, the first line contains two integers n,k, indicating the number of binary strings and the length of binary strings. In following n lines, each line contains a binary string which is in length of k.
Output
For each test case, output the answer which is the minimum times VineAsh shoule perform her magic in worst situation in a line.
Sample Input
3 1 2 00 3 4 0000 1111 1010 3 5 00000 10000 00101
Sample Output
2 2 3
Hint
1 ≤ T ≤ 10
2 ≤ k ≤ 20
1 ≤ n ≤ min(1e5, 2^k - 1)
多源BFS，傻逼题
#include<bits/stdc++.h>
using namespace std;;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e5+100;
const int INF=0x7fffffff;
int n,len,dis[(int)2e6+10];
char s[maxn][22];
int to_num(char *s){
int res=0;
rep(i,1,len) res+=(s[i]-'0')*(int)pow(2.0,len-i);
dis[res]=0;
return res;
}
void bfs(){
queue<int> q;
rep(i,1,n) q.push(to_num(s[i]));
while(!q.empty()){
int cur=q.front(); q.pop();
rep(i,0,len-1){
int nex=cur^(1<<i);
if(dis[nex]==100) dis[nex]=dis[cur]+1,q.push(nex);
}
}
}
void solve(){
scanf("%d%d",&n,&len);
rep(i,0,(1<<len)-1) dis[i]=100;
rep(i,1,n) scanf("%s",s[i]+1);
bfs();
int ans=0;
rep(i,0,(1<<len)-1) ans=max(ans,dis[i]);
printf("%d\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
Problem C
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 262144/262144K (Java/Other)
Problem Description
WNJXYK and VineAsh are friends. They often play robots together.
They have n robots in total and the i-th robot has pi sockets on it. The j-th socket on the i-th robot has its own cost Wi,j. One day, WNJXYK came out an idea connecting n robots together with a kind of special cable in order to get the strongest robot in the world. Unfortunately, WNJXYK doesn’t have this kind of cable. And, more unfortunately, VineAsh is the only person who has this kind of cable and the only person who knows how to connect two robots together with these cables in the world. Therefore, WNJXYK has no choice but to pay VineAsh some money and ask her to combine n robots into a big one. In each step of combination, VineAsh will use the cable to connect two robots together by plugging the end of this cable into a socket on each robot and then the two sockets could be no longer used. Meanwhile, WNJXYK need to pay VineAsh the sum of two sockets’ cost which she plugged.
If WNJXYK let VineAsh select sockets arbitrarily in each step, there is no doubt that he would pay VineAsh a lot of money. Therefore, WNJXYK wants to know the minimum cost he need to pay if VineAsh selects optimally in each step.
Input
The first line contains a number T, representing the number of test cases in the input.
In each test case, the first line contains an integer n, indicating the number of robots. In the following n lines, there are an integer piand pi integers wi,1,wi,2,…,wi,piin the i-th line which indicates there are pi sockets on the i-th robot and the costs of these sockets.
Output
For each test case, you should output a integer which is the minimum cost to combine all robots together. If impossible to combine all robots together, please output −1.
Sample Input
2 3 1 10 2 10 1 3 100 10 1 4 1 1 1 1 2 2 3 2 2 3
Sample Output
22 12
Hint
1 ≤ T ≤ 10
1 ≤ n ≤ 5 × 1e4
0 ≤ pi ≤ 1e5 and ∑pi<=1e5
1 ≤ wi,j ≤ 1e9
每个机器人必定要一个插座，然后在剩下的中选出2*(n-1)-n个最小的
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)5e4+100;
const int mod=(int)1e9+7;
const int INF=0x7fffffff;
int n;
vector<int> vec,tem;
void solve(){
scanf("%d",&n);
int lim=2*(n-1)-n;
vec.clear();
ll ans=0;
int flag=1;
rep(i,1,n){
int k;scanf("%d",&k);
if(k==0) flag=0;
tem.clear();
int minx=mod,pos=0;
rep(j,1,k){
int x;scanf("%d",&x);
if(x<minx) minx=x,pos=j;
tem.pb(x);
}
if(!flag) continue;
ans+=minx;
rep(pp,0,(int)tem.size()-1) if(pp!=pos-1) vec.pb(tem[pp]);
}
if((int)vec.size()<lim||flag==0) {printf("-1\n");return;}
sort(vec.begin(),vec.end());
rep(i,0,lim-1) ans+=vec[i];
printf("%lld\n",ans);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
Problem E
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 262144/262144K (Java/Other)
Problem Description
One day. an ACMer was tired of his life where he had to solve odd problems and be defeated by other teams every day. Thus he retired and bought a piece of land for planting crops. The farm he bought was a triangle area separated by two straight roads. As the picture shows, triangle ABC is his land and BD, CE are tow roads.
After several years, the ACMer forgot the size of one part of his land. Could you please tell him the size of his land?
Input
The first line of the input is a single integer T, indicates the number of the cases. Then next T lines each contains 3 integers x,y and z. They are sizes of three pieces of land that the ACMer still remembers.
Output
If the size of the last piece of land doesn't exist, print “Impossible” without quotes in a line.
Otherwise each case, output 2 integers p and q in a line, so that:
1.gcd(p,q)=1
2.p/q is the size of his land
Sample Input
3 1 1 1 1 2 3 2 3 4
Sample Output
Impossible 60 7 84 5
Hint
1 ≤ T ≤ 10000
1 ≤ x, y, z ≤ 1000000
数学
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
ll a,b,c;
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
void solve(){
scanf("%lld%lld%lld",&a,&b,&c);
ll x=a*b*c+(a+b+c)*c*c,y=c*c-a*b;
ll g=gcd(x,y);
if(y<=0) printf("Impossible\n");
else printf("%lld %lld\n",x/g,y/g);
}
int main(){
int T;cin>>T;
while(T--) solve();
}
Problem F
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 262144/262144K (Java/Other)
Problem Description
WNJXYK and VineAsh are friends. They both like drumsticks very much.
One day, VineAsh asked WNJXYK to buy some drumsticks. When WNJXYK arrived at the shop, he found that he had forgot the exact number of drumsticks VineAsh asked him to buy. And the only thing he remembered is that the number of drumsticks n can divide Aand B, which means that A%n = 0 and B%n = 0.
WXJXYK knows that if he doesn't give VineAsh enough drumsticks when he arrives home. VineAsh will stab him. Therefore, WNJXYK asks you what is the minimun number of drumsticks he needs to buy to guarantee his safety.
Input
There are multiple test cases.
The first line of input contains an integer T, representing the number of test cases.
For each test case, the first line contains two integers A,B.
Output
For each test case, output the minimum number of drumsticks WNJXYK needs to buy in a line.
Sample Input
4 1 1 2 4 3 6 4 8
Sample Output
1 2 3 4
Hint
1 ≤ T ≤ 50
1 ≤ A, B ≤ 1e5
签到
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int mod=(int)1e9+7;
int n,a,b;
int gcd(int x,int y){return y?gcd(y,x%y):x;}
void solve(){
scanf("%d%d",&a,&b);
printf("%d\n",gcd(a,b));
}
int main(){
int T;cin>>T;
while(T--) solve();
}
Problem H
Time Limit : 4000/2000ms (Java/Other) Memory Limit : 262144/262144K (Java/Other)
Problem Description
Given a network flow which has n nodes and m edges. Kayaking wants to make the maxflow from 1 to n equal or larger than C. Kayaking has the ability to increase the capacily of edges. He wants to know, in order to achieve his goal, what is the minimum sum of the increasing capacity of all edges?
Input
The first line is an integer T indicates the number of test cases.
For each test case,the first line has three integers n,m,C. Then comes m lines, each line has three integers u,v,w indicates there is an edge from u to v whose capacity is w.
Output
For each test case, output an integer.
Sample Input
2 3 3 3 1 2 2 2 3 3 1 3 1 3 3 4 1 2 2 2 3 3 1 3 1
Sample Output
0 1
Hint
1 ≤ T ≤ 1000
1 ≤ u, v, n ≤ 300, 1 ≤ m ≤ 2000
1 ≤ w ≤100
最小费用最大流模版题，建边时将每条边再额外加上一条容量无限费用为1的边，最后加一个超级汇点连接n点，容量为C以限制容量，答案即最小费用
#include<bits/stdc++.h>
using namespace std;;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e4+100;
const int INF=0x7fffffff;
struct Edge{
int to,cap,cost,next,flow;
}g[1510*1510];
int head[maxn],cnt;
int pre[maxn],dis[maxn];
bool vis[maxn];
int n,m,C;
void init(){
cnt=0;
rep(i,0,n+1) head[i]=-1;
}
void addedge(int u,int v,int cap,int cost){
g[cnt]={v,cap,cost,head[u],0};head[u]=cnt++;
g[cnt]={u,0,-cost,head[v],0}; head[v]=cnt++;
}
bool spfa(int s,int t){
queue<int> q;
for(int i=0;i<=n;++i){
dis[i]=INF; vis[i]=false; pre[i]=-1;
}
dis[s]=0; vis[s]=true;
q.push(s);
while (!q.empty()){
int u = q.front(); q.pop();
vis[u]=false;
for(int i=head[u];~i;i=g[i].next){
int v=g[i].to;
if(g[i].cap>g[i].flow&&dis[v]>dis[u]+g[i].cost){
dis[v]=dis[u]+g[i].cost;
pre[v]=i;
if(!vis[v]){
vis[v]=true;
q.push(v);
}
}
}
}
if(pre[t]==-1) return false;
else return true;
}
int MCMF(int s,int t){
int flow=0,cost=0;
while(spfa(s,t)){
int Min=INF;
for(int i=pre[t];i!=-1;i=pre[g[i^1].to]){
if(Min>g[i].cap-g[i].flow)
Min=g[i].cap-g[i].flow;
}
for(int i=pre[t];i!=-1;i=pre[g[i^1].to]){
g[i].flow+=Min;
g[i^1].flow-=Min;
cost+=g[i].cost*Min;
}
flow+=Min;
}
//return flow;
return cost;
}
void solve(){
scanf("%d%d%d",&n,&m,&C); init();
rep(i,1,m){
int u,v,c;scanf("%d%d%d",&u,&v,&c);
addedge(u,v,c,0);
addedge(u,v,INF,1);
}
addedge(n,0,C,0);
printf("%d\n",MCMF(1,0));
}
int main(){
int T;cin>>T;
while(T--) solve();
}
