2020杭電多校第二場問題解1001100610101012

1.Total Eclipse(セットを調べる)
タイトルリンク
http://acm.hdu.edu.cn/showproblem.php?pid=6763
構想
1つの連通ブロックに対してポイントウェイト値が最も小さいものを実行する必要があることは明らかであり、連通ブロックも分裂する可能性があり、連通ブロックを探すたびに最小のウェイト値を繰り返し削除すればよいが、このような状況は実現しにくいため、以下の方法では最大ウェイト値の点から逆にエッジを追加し、すなわち新規点の場合、小ウェイト値点が大きなウェイト値の点にエッジを接続する場合、小さい値を取るために必要な0になる回数は、大きな重みの点で負担できます(連通するため、重みを大きくするときに小さな重みが一緒に減少します).1、入力された点を重み値の非減算順に並べ替え、エッジを格納するコンテナを初期化し、セットを初期化し、visを初期化する.2、小重み値が大重み値に到達する場合、両者を1つに分類し、a n s−=ans−=ans−=ans−=重み値
コード#コード#

#include
#include
#include
#include
#include
using namespace std;
#define INF 0x3f3f3f3f
const int N=1e5 + 9;
pair<int,int>p[N];	//         
vector<int>g[N];	//  
int T, n, m, u, v;
long long ans;
int f[N], vis[N];

int fd(int u){
	if(f[u]==u)	return u;
	return f[u]=fd(f[u]);
}

void link(int u, int v){
	int uu=fd(u), vv=fd(v);
	if(uu!=vv)
		f[uu]=vv;
	return ;
}

void solve(){
	scanf("%d %d", &n, &m);
	for(int i=1; i<=n; i++){
		scanf("%d", &p[i].first), p[i].second=i;
		g[i].clear(), f[i]=i, vis[i]=0;
	}
	for(int i=1; i<=m; i++){
		scanf("%d %d", &u, &v);
		g[u].push_back(v), g[v].push_back(u);
	}
	sort(p+1, p+1+n);
	ans=0;
	for(int i=n; i>=1; i--){
		ans+=p[i].first;
		u=p[i].second;
		for(int it: g[u])			//       
			if(vis[it])				//         （      ）
				if(fd(it)!=fd(u))	//        
					link(u, it), ans-=p[i].first;	//    ，              
		vis[u]=1;
	}
	printf("%lld
", ans);
	return ;
}

int main(){
	scanf("%d", &T);
	while(T--)	solve();
	return 0;
}

6.The Oculus
タイトルリンク
http://acm.hdu.edu.cn/showproblem.php?pid=6768
構想
本来はA*B=Cであるが、Cの1位が0に変更されているため、A+B=C+f[k]A+B=C+f[k]A+B=C+f[k]を変換し、f[k]=A+B−C f[k]=A+B−Cを変換することで、A,B,Cの数を直接暴力的に求めることができ、ここでは非常に大きいのでハッシュを用いる必要があるが、ここでは不思議にも2^64をモジュール数として直接用いることができる.すなわちunsigned long longは、型を取る必要がなく、その型を取ると自然に溢れ出す(0から始まる).
コード#コード#

#include
#include
using namespace std;
typedef unsigned long long ull;
const int N=2e6 + 9;
ull a, b, c;
int idx;
ull f[N];

void init(){            //      
    f[1]=1ull, f[2]=2ull;
    for(ull i=3; i<=N; i++) f[i]=f[i-1]+f[i-2];
    return ;
}

ull write(){        //   A,B,C
    int x, step;
    ull ans=0;
    cin>>x;
    for(ull i=1; i<=x; i++){
        cin>>step;
        if(step==1) ans+=f[i];
    }  
    return ans;
}

void solve(){
    a=write();
    b=write();
    c=write();
    ull temp=a*b-c;     // f[k]
    for(ull j=1; ; j++){
        if(f[j]==temp) {idx=j; break;}      //             
    }
    cout<<idx<<endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
    init();
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

10.Lead of Wisdom
タイトルリンク
http://acm.hdu.edu.cn/showproblem.php?pid=6772
構想
直接暴力DFSは、それぞれのタイプを下に深く探せば終わりです
コード#コード#

#include
#include
#include
#include
using namespace std;
// #define TDS_ACM_LOCAL
const int N=59;
typedef long long ll;
struct node
{
    ll a, b, c, d;
};
vector<node>v[N];
int n, m, k, sum;
int vis[N];
ll a, b, c, d;
void init(){
    sum=0;
    for(int i=1; i<=m; i++) vis[i]=0, v[i].clear();
    return ;
}

ll dfs(int k, ll a, ll b, ll c, ll d){
    if(k==sum+1)        //    return  
        return (100ll + a)*(100ll + b)*(100ll + c)*(100ll +d);
    ll ans=0;
    for(auto it: v[k])      //      ，    
        ans=max(ans, dfs(k+1, a+it.a, b+it.b, c+it.c, d+it.d));
    return ans;
}

void solve(){
    cin>>n>>m;
    init();                     //          
    for(int i=0; i<n; i++){
        cin>>k>>a>>b>>c>>d;
        if(!vis[k]) vis[k]= ++sum;          //         
        v[vis[k]].push_back({a,b,c,d});     //        
    }
    ll ans=dfs(1, 0, 0, 0, 0);
    cout<<ans<<endl;
    return ;
}   

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

12.String Distance(dp)
タイトルリンク
http://acm.hdu.edu.cn/showproblem.php?pid=6774
構想
1、前処理a a a列中の各文字が初めて出現する位置2、クエリ区間毎に、dpはクエリ区間i番目がb列のjビットである場合、対応するaの位置を示し、<=r i g h t<=right<=right
コード#コード#

#include
#include
#include
#include
#include
using namespace std;
#define INF 0x3f3f3f3f
const int N=1e5 + 9;
char a[N], b[30];
int lena, lenb;
int loc[N][30], dp[30][30];
int T, TT, l, r, mx, ans;
void init(){
	scanf("%s %s", a+1, b+1);
	lena=strlen(a+1), lenb=strlen(b+1);
	for(int i=0; i<26; i++)		loc[lena][i]=INF;	//        
	//  a             （      ，              
	for(int i=lena-1; i>=0; i--){								
		for(int j=0; j<26; j++)	loc[i][j]=loc[i+1][j];	//            ，    a       
		loc[i][a[i+1]-'a']=i+1;								//              
	}
}

void solve(){
	init();
	scanf("%d" , &TT);
	while(TT--){
		scanf("%d %d", &l, &r);
		ans=0;
		memset(dp, INF, sizeof(dp));							//dp       i  b  j  ，   a   
		for(int j=1; j<=lenb; j++)	dp[1][j]=loc[l-1][b[j]-'a'];	//           dp

		for(int i=1; i<=lenb; i++){
			for(int j=1; j<=lenb; j++){
				if(dp[i][j]<=r){					//    
					ans=max(ans, i);				//      
					for(int k=j+1; k<=lenb; k++)
						dp[i+1][k]=min(dp[i+1][k], loc[dp[i][j]][b[k]-'a']);	//      
				}
			}
		}
		ans=(r-l+1-ans)+(lenb-ans);
		printf("%d
", ans);
	}
	return ;
}

int main(){
	scanf("%d", &T);
	while(T--)	solve();
	return 0;
}