Xâu S có độ dài không quá 100 ký tự nên bài toán này ta có thể xét hết các khả năng(vét cạn) để tìm ra chuỗi nhỏ nhất. Có rất nhiều cách giải: sử dụng thư viện chuỗi, sử dụng vector, …
Ở đây tôi sử dụng một cách giải thông thường nhất là ta sinh ra lần lượt các chuỗi từ chuỗi ban đầu rồi kiểm tra xem chuỗi vừa sinh ra có phải chuỗi nhỏ nhất không:

#include<bits/stdc++.h>
using namespace std;
string s;
int main()
{
    ifstream infile("vtay.inp");
	ofstream outfile("vtay.out");
	infile>>s;
    int n = s.size();
    string kq = s;
    for(int i=1;i<n;i++){
    	string res="";
	    for(int j=i;j<n;j++) res += s[j];
	    for(int j=0;j<i;j++) res += s[j];
    	if(kq > res) kq = res;
    }
    outfile<< kq <<endl;
    infile.close();
    outfile.close();
    return 0;
}

Thuật toán giải bài này như sau: đầu tiên ta sắp xếp các bài toán theo thứ tự kỹ năng yêu cầu rồi so sánh với năng lực. Code bài toán như sau:

#include <bits/stdc++.h>
using namespace std;
pair < int ,int > a[100001];
int n, c;
int main()
{
ifstream infile("olympic.inp");
ofstream outfile("olympic.out");
infile >> n >> c;
for(int i= 1; i<= n;i++) infile >> a[i].first >> a[i].second;
sort(a +1, a +  n + 1);
for(int i= 1; i<= n;i++)
{
if (c >= a[i].first){
c+= a[i].second;
}else
{
outfile << i-1;
return 0;
}
}
outfile << n;
infile.close();
outfile.close();
return 0;
}

Để giải quyết bài toán này, ta thực hiện các bước sau: – Dùng 2 mảng ngang – chứa trọng số các ô hàng ngang và doc – chứa trọng số các ô hàng dọc. Số phần tử của mảng ngang là n(số hàng) và số phần tử của doc là m(số cột). – Khi đọc dữ liệu vào, nếu là “H   i” thì ta tăng trọng số của ngang[i] và ngang[i+1] (vì đường bao i là đường bao chung cho cả hàng i và hàng i+1). Nếu là “V J” thì ta tăng trọng số của doc[j] và doc[j+1]. – Dùng mảng c[i] chứa số lượng các hàng ngang có i đường bao, b[j] chứa số lượng các hàng dọc có j đường bao. Với 0<=i,j<=2 – Cuối cùng, ta nhân 2 mảng c và b với nhau để được kết quả. Code như sau:

#include <iostream>
#include <fstream>
#define maxn 30000
using namespace std;
ifstream infile("roads.inp");
ofstream outfile("roads.out");
int n, m, k, v, ngang[30010], doc[30010], b[3], c[3], kq[5];
char r;
int main()
{
infile >> n >> m >> k;
for(int i=1;i<=k;i++) {
infile >> r >> v;
if (r == 'H') {ngang[v]++; ngang[v+1]++;}
else {doc[v]++; doc[v+1]++;}
}
for(int i=1;i<=n;i++) c[ngang[i]]++;
for(int i=1;i<=m;i++) b[doc[i]]++;
for(int i=0;i<=2;i++)
for(int j=0;j<=2;j++) kq[i+j] += b[i]*c[j];
for(int i=0;i<=4;i++) outfile << kq[i] << " ";
infile.close();
outfile.close();
return 0;
}

Các bạn cũng có thể giải bằng phương pháp ma trận hai chiều nhưng độ phức tạp thuật toán là nxm. Còn ở đây, độ phức tạp là max(n,m)

Nếu như chúng ta giải bài này bằng cách chạy 2 lần vòng lặp for và thử ghép cặp từng đôi một thì sẽ bị quá thời gian. Vì vậy chúng ta phải giải bằng cách khác. Ở đây, tôi thực hiện như sau:

– Trước tiên xác định xem tổng của dãy số là chẵn hay lẻ

– Nếu tổng là số lẻ thì để thu được số chẵn ta phải bỏ đi số lẻ hay bỏ đi một cặp gồm 1 số chẵn và 1 số lẻ. Ta tính được có tất cả chẵn*lẻ cặp

– Nếu tổng là số chẵn thì để thu được số chẵn ta phải bỏ đi số chẵn tức là cặp gồm 2 số cùng chẵn hoặc cùng lẻ. Ta tính được có C₂^chẵn +C₂^lẻ cặp (chẵn là số phần tử chẵn của chuỗi, lè là số phần tử lẻ của chuỗi và lẻ=n-chẵn).

Đáp án của bài toán như sau:

#include <iostream>
#include <fstream>
using namespace std;
long long a[1000000];
int main(){
ifstream infile("del.inp");
ofstream outfile("del.out");
long long n,tong=0,chan=0;
infile>>n;
for(int i=0;i<n;i++){
infile>>a[i];
tong+=a[i];
if(a[i]%2==0) chan++;
}
if(tong%2==0)    outfile<<chan*(chan-1)/2 + (n-chan)*(n-chan-1)/2;
else  outfile<<chan*(n-chan);
infile.close();
outfile.close();
return 0;
}

Hãy thử với số phần tử tối đa là 10⁶ và xem thời gian chạy bao nhiêu nhé!

Bài này về có thể giải như sau:

#include <iostream>
#include <fstream>
using namespace std;
int main(){
ifstream infile("sp.inp");
ofstream outfile("sp.out");
long long m,n,t;
infile>>m; infile>>n; infile>>t;
outfile<<((int)(n/(m+1)))*m*t + ((int)(n%(m+1)))*t;
infile.close();
outfile.close();
return 0; 
} 

Bạn nào có cách giải khác có thể comment bên dưới

Về thuật toán giải bài này không có gì rắc rối cả. Chỉ việc sắp xếp hai mảng là chỉ số năng lực của 2 đội theo thứ tự tăng dần rồi so sánh các cặp của hai mảng.

Cần chú ý là ta không nhất thiết phải viết lại hàm sắp xếp vì thư viện algorithm của C++ đã hỗ trợ sẵn. Cách sử dụng các hàm sắp xếp bạn có thể tham khảo trong file algorithm.h hoặc lên google tìm hiểu. Bạn có thể sử dụng các hàm qsort, sort, sort_heap… Ngoài ra thư viện algorithm cũng có sẵn các hàm tìm kiếm, tìm kiếm nhị phân….

Đây là code của bài toán

#include <iostream>
#include<algorithm>
#include <fstream>
using namespace std;
long long a[100000],b[100000];
long long n,res;
int main(){
    ifstream infile("fairplay.inp");
    ofstream outfile("fairplay.out");
    infile>>n;
    for(int i=0;i<n;i++){
        infile>>a[i];            
    }
    for(int i=0;i<n;i++){
        infile>>b[i];            
    }    
    sort(a,a+n);
    sort(b,b+n);
    res=0;
    int i=0,j=0;
    do{
        if(b[j]>a[i]) { i++;j++;res++;}
        else j++;
    } while(j<n);
    outfile<<res;
        infile.close();
        outfile.close();
return 0; 
} 

Nhìn chung các câu hỏi thi Olympic tin học dành cho cao đẳng đều ở mức vừa phải, không yêu cầu code dài dòng và cũng không quá phức tạp, nếu bạn chịu khó tham khảo trên các diễn đàn và các cuộc thi thì sẽ dễ dàng giải quyết

Đây là bài toán hay, có nhiều cách giải và phân loại được thí sinh rõ rệt. Có 3 bộ test với các yêu cầu ở mức khác nhau của thuật toán. Sau đây, mình xin đề xuất 3 cách giải khác nhau:

1. Cách 1: Vét cạn các khả năng. Độ phức tạp: O(n^3)

Ta chỉ đơn giản xét lần lượt các dãy con có độ dài 3,6,9,…,3k (3k<=n) và tính trọng số các dãy con đó sau đó tìm ra trọng số lớn nhất. Cách này chỉ ăn được bộ test thứ nhất. Nhưng bí quá, thì ta có thể dùng để được 1/3 số điểm của bài toán (méo mó có hơn không). Code như sau:

#include <iostream>;
#include <fstream>;
using namespace std;
long a[300001];
long tong(int pos,int num ){
    long kq=0;
    for(int i=pos; i<pos+num;i++){
        kq+=a[i];
    }
    return kq;
}
int main(){
    ifstream infile("seq.inp");
    ofstream outfile("seq.out");
    unsigned long n;
    long max=0;
    infile>>n;
    for(int i=1;i<=n;i++){
        infile>>a[i];
    }
    int k=3;
    while(k<n){
        for(int i=1;i<=n-k;i++){
            long temp = tong(i,k);
            if(temp>max)
            max=temp;
        }
        k+=3;
    }
    outfile<<max;  
    infile.close();
    outfile.close();  
    return 0;
}

2. Cách 2: Dùng quy hoạch động. Độ phức tạp O(n^2)

Gọi F[i] là trọng số lớn nhất của các đoạn con từ a[0]…a[i]

F[i] có hai khả năng:

• Không chứa phần tử a[i]. Khi đó F[i] = F[i-1]
• Chứa phần tử a[i]. Khi đó F[i] = max(g1,g2,g3…gi). Trong đó gj là tổng các giá trị của đoạn con có độ dài j kết thúc tại i. Cụ thể g[1] = a[i],
  g2 = a[i] + a[i-1]
  …
  gi = a[i] + a[i-1] +… + a[1]

Tóm lại ta có công thức truy hổi: F[i] = max(F[i-1], S1, S2,…,Si).
Kết quả của bài toán là F[n]
Độ phức tạp thuật toán là O(n^2).

Code như sau:

#include <ostream>
#include <fstream>
using namespace std;
long long a[300001],g[300001],f[300001];
int main(){
    ifstream infile("seq.inp");
    ofstream outfile("seq.out");
    unsigned long n;
    long long max=0;
    //doc du lieu tu file vao mang a va tinh mang g
    infile>>n;
    infile>>a[1]>>a[2]>>a[3];
    max=a[1]+a[2]+a[3] ;
    f[3]=max;
    for(int i=4;i<=n;i++){
        infile>>a[i];        
        g[1]=a[i];
        for(int l=2;l<=i;l++)
        {
            g[l]=g[l-1]+a[i-l+1];    //tinh s[n]
            if((l%3==0)&&(max<g[l])) max=g[l]; //chi xet nhung doan co co do dai chia het cho 3
        }
        f[i]=(f[i-1]>max)?f[i-1]:max;        
    }
    outfile<<max;
    infile.close();
    outfile.close();    
    return 0;
} 

Làm được như thế này rồi – dùng đến cả quy hoạch động rồi – ta ung dung bước ra phòng thi vểnh râu tự hào mình đã làm được bài này perfect. Nhưng chưa đâu bạn ơi, nếu làm được như thế này thì bạn mới vượt qua được bộ test thứ 2 còn bộ test thứ 3 thì vẫn quá thời gian và bạn mới được 2/3 số điểm. Làm thế nào bây giờ, còn cách nào khác gặm được bộ test thứ 3 không.?

Cách 3: Quy hoạch động cải tiến. Độ phức tạp O(n)Các bạn hãy thử cách này nhé:Gọi G[x] với G[x] = G[x – 1] + a[x];
Gọi Gmin[x] với Gmin[x] = min(G[x-1],Gmin[x – 1]);
Gọi F[x] = G[x] – minG[x];
kết quả cuối cùng = min (F[0] …. F[n – 1])
Đây là code:

#include <iostream>
#include <fstream>
using namespace std;
long long a[300001],g[300001],gmin[300001];
int main(){
ifstream infile("seq.inp");
ofstream outfile("seq.out");
unsigned long n,i,index;
infile>>n;
infile>>a[0];
g[0]=a[0];
long long max=a[0];
gmin[0]=0;
for(int i=1;i<n;i++){
infile>>a[i];
g[i]=g[i-1]+a[i];
if(gmin[i-1]>g[i-1]){
gmin[i]=g[i-1];
index=i;
}
else gmin[i]=gmin[i-1];
if((i-index+1)%3==0&&max<(g[i]-gmin[i]))    max=(g[i]-gmin[i]);
}
outfile<<max;
infile.close();
outfile.close();
return 0;
} 

Thật không thể tin nổi! Thật không thể tưởng tượng được 😀 chương trình chạy nhanh chóng hết cả mặt, với dãy số đầu vào có 300000 phần tử mà chương trình chạy hết có 0,207 giây trong khi đó yêu cầu đề bài cho tới tận 1 giây.

Ok. Nếu như bạn làm được như cách thứ 3 này thì đã có thể tự tin rằng bài của mình được điểm tuyệt đối.Bạn nào có cách giải khác tốt hơn thì đừng ngại comment lại đây nhé. Chúc các bạn thành công!