/*
二分查找
*/
#include<stdio.h>
int binarySearch(int a[],int n,int key){
int left=0;
int right=n-1;
while(left<=right){
int middle=(left+right)/2;
if(a[middle]==key) return middle;
if(key>a[middle]) left=middle+1;
else right=middle-1;
}
return -1;
}
int main(){
int n;
scanf("%d",&n);
int a[n+1];
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
int k;
scanf("%d",&k);
for(int i=0;i<k;i++){
int key;
scanf("%d",&key);
int result=binarySearch(a,n,key);
if(result!=-1)printf("%d\n",result);
else printf("NOT Found\n");
}
return 0;
}
/*
棋盘覆盖
*/
#include<bits/stdc++.h>
using namespace std;
char m[2000][2000];
void chess(int tr, int tc, int x, int y, int s)
{
if (s==1)
return;
s = s / 2;
if (x<tr+s&&y<tc+ s)//左上角
{
chess(tr, tc, x, y, s);
m[tr+s-1][tc + s] = 'd';
m[tr + s][tc + s - 1] = 'd';
m[tr + s][tc + s] = 'd';
}
else
{
chess(tr, tc, tr + s - 1, tc + s - 1, s);
}
if (x < tr + s && y>= tc + s)//右上角
{
chess(tr, tc + s, x, y, s);
m[tr + s - 1][tc + s - 1] = 'c';
m[tr + s][tc + s - 1] = 'c';
m[tr + s][tc + s] = 'c';
}
else
{
chess(tr, tc + s, tr + s - 1, tc + s, s);
}
if (x >= tr + s && y < tc + s)//左下角
{
chess(tr + s, tc, x, y, s);
m[tr + s - 1][tc + s - 1] = 'b';
m[tr + s - 1][tc + s] = 'b';
m[tr + s][tc + s] = 'b';
}
else
{
chess(tr + s, tc, tr + s, tc + s - 1, s);
}
if (x >= tr + s && y >= tc + s)//右下角
{
chess(tr + s, tc + s, x, y, s);
m[tr + s - 1][tc + s - 1] = 'a';
m[tr + s - 1][tc + s] = 'a';
m[tr + s][tc + s - 1] = 'a';
}
else
{
chess(tr + s, tc + s, tr + s, tc + s, s);
}
}
int main(){
int T,x,y,k;
cin>>T;
while(T--){
fill(m[0], m[0]+2000*2000,'0');
cin>>k>>x>>y;
int s=pow(2,k);
x--;
y--;
chess(0,0,x,y,s);
for (int i = 0; i < s; i++)
{
for (int c = 0; c < s; c++)
{
if(i==x&&c==y){
cout<<"*";
}
else{
cout<<m[i][c];
}
}
cout<<"" <<endl;
}
}
}
/*
活动安排
*/
#include<stdio.h>
int main(){
int n,k;
int a[1002],b[1002];
scanf("%d",&n);
int sum=0;
while(n>0){
scanf("%d",&k);
for(int i=0;i<k;i++){
scanf("%d%d",&a[i],&b[i]);
}
for(int i=0;i<k;i++)
for(int j=0;j<k;j++)
{
if(b[i]<b[j])
{
int temp=b[i];
b[i]=b[j];
b[j]=temp;
int temp1=a[i];
a[i]=a[j];
a[j]=temp1;
}
}
int count=1;
int m=0;
for(int i=1;i<k;i++)
{
if(b[m]<=a[i])
{
count++;
m=i; }
}
sum++;
printf("Case %d: %d\n",sum,count);
n--;
}
return 0;
}
/*
最优装载
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,w;
int a[1002];
cin>>n;
int sum=0;
for( w=1;w<=n;w++){
int v,k;
//集装箱个数 载重量
cin>>v>>k;
for(int i=0;i<v;i++){
// scanf("%d",&a[i]);
cin>>a[i];
}
sort(a,a+v);
int count=0,sum=0;
for(int i=0;i<v;i++)
{
if(k-a[i]>=0)
{
count+=a[i];
k-=a[i];
sum++;
}
}
cout<<"Case "<<w<<": "<<sum<<" "<<count<<endl;
}
return 0;
}
/*
多机调度
*/
#include<bits/stdc++.h>
using namespace std;
int s[1002]={0};
int main(){
int n,t,maxtime=0;
int a[10000]={0};
int w,count=1;
cin>>w;
for(int i=1;i<=w;i++){
maxtime=0;
memset(a,0,sizeof(a));
memset(s, 0, sizeof(s));
cin>>n>>t;
for(int i=0;i<n;i++)
cin>>a[i];
sort(a,a+n);
reverse(a,a+n);
if(n<=t){//作业数小于机器数 最大运行时间为最大值
maxtime=a[0];
}
else{//作业数大于机器数
for(int i=0;i<n;i++){
sort(s,s+t);
s[0]+=a[i];
}
sort(s,s+t);
maxtime=s[t-1];
}
cout<<"Case "<<count<<": "<<maxtime<<endl;
count++;
}
return 0;
}
#include<bits/stdc++.h>
using namespace std;
const long long inf=0x3f3f3f3f;
const int maxn=700;
int dp[maxn][maxn],t,p[maxn],step,n;
int main(){
cin>>t;
while(t--){
fill(dp[0],dp[0]+maxn*maxn,inf);
fill(p,p+maxn,0);
cin>>n;
int a,b;
//输入矩阵
for(int i=1;i<=n;i++){
cin>>a>>b;
if(i==1){
p[0]=a;
p[1]=b;
}
else p[i]=b;
}
for(int i=1;i<=n;i++) dp[i][i]=0;//对角线置为0
for(int r=2;r<=n;r++)
for(int i=1;i<=n-r+1;i++){
int j=i+r-1;
for(int k=i;k<=j;k++){
step=dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j];
dp[i][j]=min(dp[i][j],step);
}
}
cout<<dp[1][n]<<endl;
}
return 0;
}
/*
最长公共子序列
*/
#include<bits/stdc++.h>
using namespace std;
char x[1005],y[1005];
int DP[1005][1005];
int main(){
int n;
cin>>n;
while(n--){
int x1,y1;
cin>>x>>y;
x1=strlen(x);
y1=strlen(y);
memset(DP,0,sizeof(DP));
for(int i=1;i<=x1;i++){
for(int j=1;j<=y1;j++){
if(x[i-1]==y[j-1]) DP[i][j]=DP[i-1][j-1]+1;
else DP[i][j]=max(DP[i-1][j],DP[i][j-1]);
}
}
cout<<DP[x1][y1]<<endl;
}
}
/*
01背包
*/
#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int n,c;
int w[N],v[N];
int ans;
//搜到第u件物品 这个方案的总重uw总价uv
void DFS(int u,int uw,int uv) {
if(u==n+1)
{
// 搜完所有n件物品
ans=max(ans,uv);
return;
}
if(uw+w[u]<=c)
DFS(u+1,uw+w[u],uv+v[u]);
DFS(u+1,uw,uv);
}
int main()
{
int t;
cin>>t;
while(t--) {
cin>>n>>c;
for(int i=1;i<=n;i++){
cin>>w[i]>>v[i];
}
ans=0; DFS(1,0,0);
cout<<ans<<endl;
}
return 0;
}
/*
装载问题
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1000+5;
int n,c1,c2;
int sum,w[N];
int ans;
void DFS(int u,int c){
if(u>n) {// 搜完所有n个集装箱
ans=max(ans,c);// 更新不超重的情况下c1装的最大重量
return;
}
if(c+w[u]<=c1)// 总重不超重就可以装在c1
DFS(u+1,c+w[u]);
// 不装在c1
DFS(u+1,c);
}
int main(){
int T;
cin>>T;
int k=0;
while(k!=T){
cin>>n>>c1>>c2;
sum=0; // sum是n个集装箱的总重
for(int i=1;i<=n;i++){
cin>>w[i];
sum+=w[i];
}
ans=0;
DFS(1,0);
printf("Case %d:\n",k);
// 搜完后 最多装在c1的重量是ans sum-ans是装在c2的重量
// c1确定不超重 若c2也不超重就说明存在最优装载方案
if(sum-ans<=c2) cout<<ans<<endl;
else cout<<"No"<<endl;
k++;
}
return 0;
}
/*
n后问题
*/
#include<bits/stdc++.h>
using namespace std;
int now,sum;
int a[100];
bool flag;
void f(int n){
if(n==now) sum++;
else{
for(int i=0;i<now;i++){
a[n]=i;
flag=true;
for(int j=0;j<n;j++){
if(a[n]==a[j]||n-j==a[n]-a[j]||n-j==a[j]-a[n]){
flag=false;
break;
}
}
if(flag) f(n+1);
}
}
}
int main(){
int t;
cin>>t;
while(t--){
memset(a,0,sizeof(a));
cin>>now;
sum=0;
f(0);
cout<<sum<<endl;
}
}
/*
旅行售货员问题（回溯、分枝限界）
*/
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int N=20;
int n,m,G[N][N];
int id[N],ans;
void DFS(int u,int w){
if(w>ans) return;
if(u==n+1) { // 搜完走所有n个点的顺序了
if(G[id[n]][1]!=INF) // 如果能回到点1
ans=min(ans,w+G[id[n]][1]); // 总花费尝试更新最小花费
return;
}
for(int i=u;i<=n;i++)
if(G[id[u-1]][id[i]]!=INF) {
// 上一步走到id[u-1] 这一步走id[i] 有路可走
// 这一步是第u步 走的是id[i] 让id[u]里存着第u步走的点 所以交换两个位置里的值
swap(id[i],id[u]); // 交换能保证id[]里的u+1~n都是还没有走过的点
DFS(u+1,w+G[id[u-1]][id[u]]); // 这一步走id[i]
swap(id[i],id[u]); // 取消交换 尝试这一步先走其他点的方案
}
}
int main(){
int T;
cin>>T;
int k=0;
while(k!=T){
k++;
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
G[i][j]=INF;
while(m--){
int u,v,w;
cin>>u>>v>>w;
G[u][v]=G[v][u]=w;
}
ans=INF;
for(int i=1;i<=n;i++)
id[i]=i;
DFS(2,0);
cout<<"Case "<<k<<": ";
if(ans==INF) cout<<"-1"<<endl;
else cout<<ans<<endl;
}
return 0;
}
