Day1

T1

#include<bits/stdc++.h> 
using namespace std;
int main(){
	freopen("mod.in","r",stdin);
	freopen("mod.out","w",stdout);
	long long n;
	cin>>n;
    if(n%2) cout<<(n+1)/2*(n/2);
    else cout<<(n/2+1)*(n/2-1);
	return 0;
}

T2

#include<bits/stdc++.h> 
using namespace std;
int n;
string s;
int main(){
	freopen("number.in","r",stdin);
	freopen("number.out","w",stdout);
	cin>>n;
	cin>>s;
    long long sum=0;
    for(int i=0;i<=s.size()-1;i++){
        if(s[i]>='0' && s[i]<='9'){ 
            long long sum2=0;          
            while(s[i]>='0' && s[i]<='9'){
                sum2=sum2*10+s[i]-'0';
                i++;
            }
            sum2+=5;
            sum+=sum2;
        }
    }
    cout<<sum;
	return 0;
}

T3

#include <bits/stdc++.h>
using namespace std;
int n,a[100010],c[100010];
int m,cnt,mp[450][100010],b[450];
int zh(int x,int y){
	if(x==1) return y;
	if(x==2) return y*(y-1)/2;
	if(x==3) return y*(y-1)*(y-2)/6;
	if(x==4) return y*(y-1)*(y-2)*(y-3)/24;
}
int main(){
	freopen("wq.in","r",stdin);
	freopen("wq.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]>n) continue;
		c[a[i]]++;
		if(c[a[i]]==a[i]) b[++cnt]=a[i];
	}
	for(int i=1;i<=cnt;i++){
		for(int j=1;j<=n;j++){
			if(a[j]==b[i]) mp[i][j]=mp[i][j-1]+1;
			else mp[i][j]=mp[i][j-1];
		}
	}
	cin>>m;
	for(int i=1;i<=m;i++){
		int l,r,k,sum=0;
		cin>>l>>r>>k;
		for(int j=1;j<=cnt;j++){
			if(mp[j][r]-mp[j][l-1]>=b[j]) 
                sum++;
		}
		cout<<zh(k,sum)<<endl;
	}
	return 0;	
}

T4

#include <bits/stdc++.h>
using namespace std;

int n,a,b;
string s;
int pi[1005];
int dp[1005][1005][3][3];


void solve()
{
	cin>>n>>a>>b>>s;
	s=" "+s;
	stack<int>st;
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='(')st.push(i);
		else 
		{
			pi[i]=st.top();
			pi[st.top()]=i;
			st.pop();
		}
	}

	for(int len=2;len<=n;len+=2)
	{
		for(int l=1,r=len;r<=n;l++,r++)
		{
			if(s[l]==')' || s[r]=='(')continue;
			if(pi[l]==r)
			{
				if(len==2)
				{
					dp[l][r][0][0]=0;
					dp[l][r][1][1]=a;
					dp[l][r][2][2]=b;
				}else if(pi[l+1]==r-1)
				{
					dp[l][r][0][0]=0+max(dp[l+1][r-1][1][1],dp[l+1][r-1][2][2]);
					dp[l][r][1][1]=a+max(dp[l+1][r-1][0][0],dp[l+1][r-1][2][2]);
					dp[l][r][2][2]=b+max(dp[l+1][r-1][0][0],dp[l+1][r-1][1][1]);
				}else
				{
					for(int i=0;i<=2;i++)
					{
						for(int j=0;j<=2;j++)
						{
							if(i!=0&&j!=0)dp[l][r][0][0]=max(dp[l][r][0][0],dp[l+1][r-1][i][j]);
							if(i!=1&&j!=1)dp[l][r][1][1]=max(dp[l][r][1][1],dp[l+1][r-1][i][j]);
							if(i!=2&&j!=2)dp[l][r][2][2]=max(dp[l][r][2][2],dp[l+1][r-1][i][j]);
						}
					}
					dp[l][r][0][0]+=0;
					dp[l][r][1][1]+=a;
					dp[l][r][2][2]+=b;
				}
			}else
			{
				if(pi[l]==pi[r]-1)
				{
					for(int i=0;i<=2;i++)
					{
						for(int j=0;j<=2;j++)
						{
							if(i==j)continue;
							dp[l][r][i][j]=dp[l][pi[l]][i][i]+dp[pi[r]][r][j][j];
						}
					}
				}else
				{
					for(int i=0;i<=2;i++)
					{
						for(int j=0;j<=2;j++)
						{
							for(int t1=0;t1<=2;t1++)
							{
								if(t1==i)continue;
								dp[l][r][i][j]=max(dp[l][r][i][j],dp[l][pi[l]][i][i]+dp[pi[l]+1][r][t1][j]);
							}
						}
					}
				}
			}
		}
	}
	int mx=0;
	for(int i=0;i<=2;i++)
	{
		for(int j=0;j<=2;j++)
		{
			mx=max(mx,dp[1][n][i][j]);
		}
	}
	cout<<mx;
}
int main()
{
	freopen("bracket.in", "r", stdin);
	freopen("bracket.out", "w", stdout);
	solve();
	return 0;
}

Day2

T1

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct node{
    int t;
    int v;
};
node a[N];
int n,k;
long long ans;
bool cmp(node a,node b){
    return a.v>b.v;
}
int main(){
    freopen("coin.in", "r", stdin);
    freopen("coin.out", "w", stdout);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i].t;
    for(int i=1;i<=n;i++) cin>>a[i].v;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=k;i++){
        ans+=a[i].v;
    }
    cout<<ans;
    return 0;
}

T2

#include<bits/stdc++.h>
using namespace std;
long long max;
bool cmp(string a,string b){
	return a>b;
}
int f(string a,string b){
	int idx=0;
	int len=a.size();
	for(int i=0;i<len;i++){
		if(a[i]!=b[i]){
			idx=i;
			break;
		}
	}
	return idx+1;
}
int main(){
	freopen("mul.in","r",stdin);
	freopen("mul.out","w",stdout);
	string a,b;
	cin>>a>>b;
	if(!cmp(a,b)) swap(a,b);
	int len=a.size();
	int idx=f(a,b);
	for(int i=idx;i<len;i++){
		if(a[i]>b[i]) swap(a[i],b[i]);
	}
	long long n=0,m=0;
	for(int i=0;i<len;i++){
        n=n*10+a[i]-'0';
		m=m*10+b[i]-'0';
	}
	cout<<n*m;
	return 0;
}

T3

#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<int> v1;

vector<int> div(vector<int> a, int b){
	vector<int> res;
	int t=0;
	int r=0;
    int len=a.size()-1;
	for(int i=len;i>=0;i--){
		t=r*10+a[i];
		res.push_back(t/b);
		r=t%b;
	}
	reverse(res.begin(),res.end());
    while(res.size()>1 && res.back()==0) res.pop_back();
	return res;
}

signed main(){
    freopen("drink.in","r",stdin);
    freopen("drink.out","w",stdout);
	string n;
    cin>>n;
    int k;
    cin>>k;
	int len=n.size();
	for(int i=len-1;i>=0;i--)
		v1.push_back(n[i]-'0');
	auto C=div(v1, k-1);
	int len2=C.size();
	for(int i=len2-1;i>=0;i--){
		cout << C[i];
	}
	return 0;
}

T4

#include<bits/stdc++.h>
using namespace std ;
int main() 
{
	freopen("op.in", "r", stdin);
	freopen("op.out", "w", stdout);
    //std::ios::sync_with_stdio(false) , cin.tie(0) ;

    int n , k ;
    cin >> n >> k ;
    vector<int> p(n + 1 , 0) ;    
    vector<int> t(n + 1 , 0) ;    
    vector<int> a(n + 1 , 0) ;    
    vector<int> b(n + 1 , 0) ;    
    for(int i = 1 ; i <= n ; i ++)  cin >> p[i] ;
    for(int i = 1 ; i <= n ; i ++)  cin >> t[i] ;
    for(int i = 1 ; i <= n ; i ++)  cin >> a[i] ;
    for(int i = 1 ; i <= n ; i ++)  cin >> b[i] ;
    vector<int> id(n + 1 , 0) ;
    for(int i = 1 ; i <= n ; i ++)  id[i] = i ;
    sort(id.begin() + 1 , id.end() , [&](int x , int y)
    {
        return p[x] < p[y] ;
    }) ;
    set<pair<int , int>> s ;
    s.insert({1 , k}) ;
    long long res = 0 ;
    for(int i = 1 ; i <= n ; i ++)
    {
        int c = id[i] ;
        if(s.empty())  break ;
        auto it = s.lower_bound({t[c] , 0}) ;
        auto it2 = it ;
        if(it2 != s.begin())  it2 -- ;
        if(it2 -> first <= t[c] && t[c] <= it2 -> second)  it = it2 ;
        if(it != s.end())
        {
            t[c] = max(t[c] , it -> first) ;
            if(t[c] <= it -> second)
            {
                if(it -> first < t[c])
                {
                    int l = it -> first ;
                    int r = it -> second ;
                    s.erase({l , r}) ;
                    s.insert({l , t[c] - 1}) ;
                    s.insert({t[c] , r}) ;
                    it = s.lower_bound({t[c] , 0}) ;
                }
                vector<pair<int , int>> v ;
                while(it != s.end())
                {
                    int l = it -> first ;
                    int r = it -> second ;
                    if(r - l + 1 >= b[c])
                    {
                        res += a[c] ;
                        s.erase(it) ;
                        if(r - l + 1 > b[c])  s.insert({l + b[c] , r}) ;
                        break ;
                    }
                    else
                    {
                        v.push_back({l , r}) ;
                        it ++ ;
                    }
                }
                for(auto now : v)  s.erase(now) ;
            }
        }
    }
    cout << res  ;

    return 0 ;
}

Day3

T1

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
bool cmp(int a,int b){
    return a<b;
}
int main(){
    freopen("divmod.in", "r", stdin);
    freopen("divmod.out", "w", stdout);
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    if(k==1){
        if(n==1){
            cout<<a[1];
            return 0;
        }
        sort(a+1,a+1+n,cmp);
        long long sum=0;
        for(int i=2;i<=n;i++){
            sum+=a[i];
        }
        long long ans=sum-a[1];
        cout<<ans;
    }
    else{
        if(n==1){
            cout<<a[1];
            return 0;
        }
        sort(a+1,a+1+n);
        long long sum=a[1];
        for(int i=2;i<=n;i++){
            sum=sum%a[i];
        }
        cout<<sum;
    }
    return 0;
}

T2

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
bool flag[N];
int main(){
    freopen("hw.in", "r", stdin);
    freopen("hw.out", "w", stdout);
    string s;
    cin>>s;
    s=' '+s;
    int len=s.size()-1;
    int cnt=0;
    for(int i=1;i<=len/2;i++){
        if(s[i]!=s[len-i+1]){
            char ch=min(s[i],s[len-i+1]);
            s[i]=ch;
            s[len-i+1]=ch;
            flag[i]=true;
            cnt++;
        }
    }
    for(int i=1;i<=len/2;i++){
        if(cnt==2) break;
        if(flag[i] && cnt<2 && s[i]!='a'){
            s[i]='a';
            s[len-i+1]='a';
            cnt+=1;
        }else if(cnt==0 && s[i]!='a'){
            s[i]='a';
            s[len-i+1]='a';
            cnt+=2;
        }
    }
    if(cnt<=1 && len%2==1){
        s[len/2+1]='a';
    }
    cout<<s.substr(1);
    return 0;
}

T3

#include<bits/stdc++.h>
using namespace std;
int a[1000010];
bool b[2000010];
long long n,cnt;
void f(){
	for(int i=2;i<=2000000;i++){
		if(b[i]) continue;
		for(int j=2*i;j<=2000000;j+=i){
			b[j]=1;
		}
	}
	return ;
}
int main(){
 	freopen("color.in","r",stdin);
	freopen("color.out","w",stdout); 
	cin>>n;
	f();
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	long long u,v;
	for(int i=1;i<n;i++){
		cin>>u>>v;
		if(b[a[u]+a[v]]){
			cnt++;
		}
	}
	cout<<n-1-cnt;
	return 0;
}

T4

#include<bits/stdc++.h>
using namespace std;
long long n, f[10], tmp, ans=0;
int main(){
	freopen("div.in", "r", stdin);
	freopen("div.out", "w", stdout);
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> tmp;
		for(int j = 1; j <= 5; j++)
			f[j] += ((tmp / j) > (tmp % j) && (tmp/1000000 <= j));
	}
	for(int i = 1; i <= 5; i++) ans = max(ans, f[i]);
	cout << ans;
	return 0;
}

Day4

T1

#include<bits/stdc++.h>
using namespace std;
const int N=3e3+5;
int n,l,r,k;
int a[N];
int main(){
    freopen("mod.in", "r", stdin);
    freopen("mod.out", "w", stdout);
    cin>>n>>l>>r;
    for(int i=1;i<=n;i++) cin>>a[i];
    int minn=2e7;
    for(int i=l;i<=r;i++){
        int sum=0;
        for(int j=1;j<=n;j++){
            sum+=a[j]%i;
        }
        if(sum<minn){
            k=i;
            minn=sum;
        }
    }
    cout<<k;
    return 0;
}

T2

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int q[10] = {1, 10, 5, 10, 5, 2, 5, 10, 5, 10};
int t, k[N];
long long a[N];
int main() {
	freopen("mul.in", "r", stdin);
	freopen("mul.out", "w", stdout);
	cin >> t;
	for (int i = 1; i <= t; i++) {
		cin >> a[i] >> k[i];
		long long n = 0, m = 0, ans = 1;
		while (a[i] % 10 == 0) {
			a[i] /= 10;
			m ++;
		}
		n = a[i] % 10;
		if (m >= k[i]) {
			cout << 1 << endl;
			continue;
		}
		while (m < k[i]) {
			ans *= q[n];
			a[i] *= q[n];
			n = (a[i] / 10) % 10;
			a[i] /= 10;
			m++;
		}
		cout << ans << endl;
	}
	return 0;
}

T3

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,q,cnt[N][30],book[N],res;
char c[N];
void dfs(int i){
    if(2*i<=n){
        dfs(i*2);
        for(int j=0;j<26;j++) cnt[i][j]+=cnt[2*i][j];
    }
    if(2*i+1<=n){
        dfs(i*2+1);
        for(int j=0;j<26;j++) cnt[i][j]+=cnt[2*i+1][j];
    }
    cnt[i][c[i]-'a']++;
    int temp=0;
    for(int j=0;j<26;j++) temp+=(cnt[i][j]%2);
    if(temp<=1){
        res++;
        book[i]=1;
    }
}
void up(int i,char now,char old){
    while(i){
        cnt[i][old-'a']--;
        cnt[i][now-'a']++;
        int temp=0;
        for(int j=0;j<26;j++) temp+=(cnt[i][j]%2);
        if(temp<=1){
            if(!book[i]) res++;
            book[i]=1;
        }else{
            if(book[i]) res--;
            book[i]=0;
        }
        i/=2;
    }
}
int main(){
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>c[i];
    dfs(1);
    cout<<res<<endl;
    while(q--){
        int x;
        char ch;
        cin>>x>>ch;
        up(x,ch,c[x]);
        c[x]=ch;
        cout<<res<<endl;
    }
    return 0;
}

T4

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int a[N];
int n,t;
signed main(){
    freopen("gz.in", "r", stdin);
    freopen("gz.out", "w", stdout);
    cin>>n;
    long long sum=n*(n-1)/4;
    for(int i=1;i<=n;i++){
        if(sum>=n-i){
            a[i]=i;
            sum-=n-i;
        }else{
            a[i]=n-sum;
            t=i+1;
            break;
        }
    }
    for(int i=t,x=n;i<=n;i++,x--){
        if(x==n-sum) x--;
        a[i]=x;
    }
    for(int i=1;i<=n;i++) cout<<a[i]<<" ";
    return 0;
}