What will the whole array satisfy? Is that a sufficient condition?

#include <cstdio>
static const int MAXN = 102;

int n;
int a[MAXN];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);

    puts((n % 2 == 1) && (a[0] % 2 == 1) && (a[n - 1] % 2 == 1) ? "Yes" : "No");
    return 0;
}

First way: consider the first three points. What cases are there?

Second way: consider the first point. Either it's on a single line alone, or the line that passes through it passes through another point. Iterate over this point.

#include <bits/stdc++.h>
#define eps 1e-7
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,a[1007];
bool vis[1007];
bool check(double k,int b)
{
	memset(vis,false,sizeof(vis));
	int cnt=0;
	for (int i=1;i<=n;i++)
	{
		if (a[i]-b==1LL*k*(i-1)) 
		{
			vis[i]=true;
			++cnt;
		}
	}
	if (cnt==n) return false;
	if (cnt==n-1) return true;
	int pos1=0;
	for (int i=1;i<=n;i++)
		if (!vis[i]&&pos1==0) pos1=i;
	for (int i=pos1+1;i<=n;i++)
		if (!vis[i])
		{
			if (fabs((double)(a[i]-a[pos1])/(i-pos1)-k)>eps) return false;
		}
	return true;
}
int main()
{
	n=read();
	for (int i=1;i<=n;i++)
		a[i]=read();
	bool ans=false;
	ans|=check(1.0*(a[2]-a[1]),a[1]);
	ans|=check(0.5*(a[3]-a[1]),a[1]);
	ans|=check(1.0*(a[3]-a[2]),a[2]*2-a[3]);
	if (ans) printf("Yes\n"); else printf("No\n");
	return 0;
}

#include <cstdio>
#include <algorithm>
static const int MAXN = 1004;

int n;
int y[MAXN];

bool on_first[MAXN];

bool check()
{
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if ((long long)i * (y[j] - y[0]) == (long long)j * (y[i] - y[0]))
                on_first[j] = true;
            else on_first[j] = false;
        }
        int start_idx = -1;
        bool valid = true;
        for (int j = 0; j < n; ++j) if (!on_first[j]) {
            if (start_idx == -1) {
                start_idx = j;
            } else if ((long long)i * (y[j] - y[start_idx]) != (long long)(j - start_idx) * (y[i] - y[0])) {
                valid = false; break;
            }
        }
        if (valid && start_idx != -1) return true;
    }
    return false;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &y[i]);

    bool ans = false;
    ans |= check();
    std::reverse(y, y + n);
    ans |= check();

    puts(ans ? "Yes" : "No");
    return 0;
}

For a given string, how to calculate the cost?

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;

#ifdef WIN32
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

int main()
{
    int k;
    scanf("%d", &k);
    for (int i = 0; i < 26; i++)
    {
        int cnt = 1;
        while ((cnt + 1) * cnt / 2 <= k) cnt++;
        k -= cnt * (cnt - 1) / 2;
        for (int j = 0; j < cnt; j++) printf("%c", 'a' + i);
    }
    return 0;
}

#include <cstdio>
#include <vector>
static const int MAXK = 100002;
static const int INF = 0x3fffffff;

int f[MAXK];
int pred[MAXK];

int main()
{
    f[0] = 0;
    for (int i = 1; i < MAXK; ++i) f[i] = INF;
    for (int i = 0; i < MAXK; ++i) pred[i] = -1;

    for (int i = 0; i < MAXK; ++i) if (f[i] != INF) {
        for (int j = 2; i + j * (j - 1) / 2 < MAXK; ++j)
            if (f[i + j * (j - 1) / 2] > f[i] + 1) {
                f[i + j * (j - 1) / 2] = f[i] + 1;
                pred[i + j * (j - 1) / 2] = j;
            }
    } else printf("Assertion failed at %d\n", i);

    int k;
    scanf("%d", &k);
    if (k == 0) { puts("a"); return 0; }
    std::vector<int> v;
    for (; k > 0; k -= pred[k] * (pred[k] - 1) / 2) {
        v.push_back(pred[k]);
    }
    for (int i = 0; i < v.size(); ++i) {
        for (int j = 0; j < v[i]; ++j) putchar('a' + i);
    }
    putchar('\n');

    return 0;
}

When do dancers collide? What changes and what keeps the same?

#include <cstdio>
#include <algorithm>
#include <vector>
static const int MAXN = 100004;
static const int MAXW = 100003;
static const int MAXT = 100002;

int n, w, h;
int g[MAXN], p[MAXN], t[MAXN];

std::vector<int> s[MAXW + MAXT];
int ans_x[MAXN], ans_y[MAXN];

int main()
{
    scanf("%d%d%d", &n, &w, &h);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d%d", &g[i], &p[i], &t[i]);
        s[p[i] - t[i] + MAXT].push_back(i);
    }

    std::vector<int> xs, ys;
    for (int i = 0; i < MAXW + MAXT; ++i) if (!s[i].empty()) {
        for (int u : s[i]) {
            if (g[u] == 1) xs.push_back(p[u]);
            else ys.push_back(p[u]);
        }
        std::sort(xs.begin(), xs.end());
        std::sort(ys.begin(), ys.end());
        std::sort(s[i].begin(), s[i].end(), [] (int u, int v) {
            if (g[u] != g[v]) return (g[u] == 2);
            else return (g[u] == 2 ? p[u] > p[v] : p[u] < p[v]);
        });
        for (int j = 0; j < xs.size(); ++j) {
            ans_x[s[i][j]] = xs[j];
            ans_y[s[i][j]] = h;
        }
        for (int j = 0; j < ys.size(); ++j) {
            ans_x[s[i][j + xs.size()]] = w;
            ans_y[s[i][j + xs.size()]] = ys[ys.size() - j - 1];
        }
        xs.clear();
        ys.clear();
    }

    for (int i = 0; i < n; ++i) printf("%d %d\n", ans_x[i], ans_y[i]);

    return 0;
}

Difference between last occurrence and first occurrence equals the sum of differences between pairs of adjacent occurrences. Handle this with some segment tree, or even non-standard size block decomposition, say sizes of O(n^1 / 3).

#include <bits/stdc++.h>

#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define forn(i, n) fore(i, 0, n)

#define all(a) (a).begin(), (a).end()
#define sqr(a) ((a) * (a))
#define sz(a) int(a.size())
#define mp make_pair
#define pb push_back

#define x first
#define y second

using namespace std;

template<class A, class B> ostream& operator << (ostream &out, const pair<A, B> &p) {
	return out << "(" << p.first << ", " << p.second << ")";
}

template<class A> ostream& operator << (ostream &out, const vector<A> &v) {
	out << "[";
	forn(i, sz(v)) {
		if(i > 0)
			out << " ";
		out << v[i];
	}
	return out << "]";
}

mt19937 myRand(time(NULL));

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

inline int gett() {
	return clock() * 1000 / CLOCKS_PER_SEC;
}

const ld EPS = 1e-9;
const int INF = int(1e9);
const li INF64 = li(INF) * INF;
const ld PI = 3.1415926535897932384626433832795;

const int N = 100 * 1000 + 555;

int n, m, aa[N], a[N];
int qt[N], qx[N], qy[N];

inline bool read() {
	if(!(cin >> n >> m))
		return false;
	
	forn(i, n)
		assert(scanf("%d", &aa[i]) == 1);
		
	forn(i, m) {
		assert(scanf("%d%d%d", &qt[i], &qx[i], &qy[i]) == 3);
		qx[i]--;
	}
		
	return true;
}

vector<int> vars[4 * N];
vector<li> f[4 * N];
li sumAll[4 * N];

inline void addValF(int k, int pos, int val) {
	sumAll[k] += val;
	for(; pos < sz(f[k]); pos |= pos + 1)
		f[k][pos] += val;
}

inline li sum(int k, int pos) {
	li ans = 0;
	for(; pos >= 0; pos = (pos & (pos + 1)) - 1)
		ans += f[k][pos];
		
	return ans;
}

inline li getSumF(int k, int pos) {
	return sumAll[k] - sum(k, pos - 1);
}

li getSumST(int v, int l, int r, int lf, int rg, int val) {
	if(l >= r || lf >= rg)
		return 0;
		
	if(l == lf && r == rg) {
		int pos = int(lower_bound(all(vars[v]), val) - vars[v].begin());
		return getSumF(v, pos);
	}
	
	int mid = (l + r) >> 1;
	
	li ans = 0;
	if(lf < mid)
		ans += getSumST(2 * v + 1, l, mid, lf, min(mid, rg), val);
	if(rg > mid)
		ans += getSumST(2 * v + 2, mid, r, max(lf, mid), rg, val);
		
	return ans;
}

void addValST(int k, int v, int l, int r, int pos, int pos2, int val) {
	if(l >= r)
		return;
		
	if(!k)
		vars[v].pb(pos2);
	else {
		int cpos = int(lower_bound(all(vars[v]), pos2) - vars[v].begin());
		addValF(v, cpos, val);
	}
	
	if(l + 1 == r) {
		assert(l == pos);
		return;
	}
	
	int mid = (l + r) >> 1;
	
	if(pos < mid)
		addValST(k, 2 * v + 1, l, mid, pos, pos2, val);
	else
		addValST(k, 2 * v + 2, mid, r, pos, pos2, val);
}

int pr[N];
set<int> ids[N];

void build(int k, int v, int l, int r) {
	fore(i, l, r)
		if(!k)
			vars[v].pb(pr[i]);
		else {
			int pos = int(lower_bound(all(vars[v]), pr[i]) - vars[v].begin());
			addValF(v, pos, i - pr[i]);
		}
			
	if(l + 1 == r)
		return;
		
	int mid = (l + r) >> 1;
	
	build(k, 2 * v + 1, l, mid);
	build(k, 2 * v + 2, mid, r);
}

inline void eraseSets(int k, int pos) {
	addValST(k, 0, 0, n, pos, pr[pos], -(pos - pr[pos]));
	ids[ a[pos] ].erase(pos);
	
	auto it2 = ids[ a[pos] ].lower_bound(pos);
	
	if(it2 != ids[ a[pos] ].end()) {
		int np = *it2;
		assert(a[np] == a[pos]);
		assert(pr[np] == pos);
		
		addValST(k, 0, 0, n, np, pr[np], -(np - pr[np]));
		
		pr[np] = pr[pos];
		addValST(k, 0, 0, n, np, pr[np], +(np - pr[np]));
	}
	
	a[pos] = -1;
	pr[pos] = -1;
}

inline void insertSets(int k, int pos, int nval) {
	auto it2 = ids[nval].lower_bound(pos);
	assert(it2 == ids[nval].end() || *it2 > pos);
	
	if(it2 != ids[nval].end()) {
		int np = *it2;
		assert(a[np] == nval);
		
		addValST(k, 0, 0, n, np, pr[np], -(np - pr[np]));

		pr[np] = pos;
		addValST(k, 0, 0, n, np, pr[np], +(np - pr[np]));
	}
	
	pr[pos] = -1;
	if(it2 != ids[nval].begin()) {
		auto it1 = it2; it1--;
		assert(*it1 < pos);
		
		pr[pos] = *it1;
	}
	addValST(k, 0, 0, n, pos, pr[pos], +(pos - pr[pos]));
	
	ids[nval].insert(pos);
	a[pos] = nval;
}

inline void precalc() {
	forn(v, 4 * N) {
		sort(all(vars[v]));
		vars[v].erase(unique(all(vars[v])), vars[v].end());
		
		f[v].assign(sz(vars[v]), 0);
		sumAll[v] = 0;
	}
}

inline void solve() {
	forn(k, 2) {
		if(k) precalc();
		
		forn(i, N)
			ids[i].clear();
		forn(i, n)
			a[i] = aa[i];
			
		vector<int> ls(n + 1, -1);
		forn(i, n) {
			pr[i] = ls[ a[i] ];
			ls[ a[i] ] = i;
			
			ids[ a[i] ].insert(i);
		}
		
		build(k, 0, 0, n);
		
//		cerr << k << " " << clock() << endl;
		
		forn(q, m) {
			if(qt[q] == 1) {
				eraseSets(k, qx[q]);
				insertSets(k, qx[q], qy[q]);
			} else
				if(k) printf("%I64d\n", getSumST(0, 0, n, qx[q], qy[q], qx[q]));
		}
		
//		cerr << k << " " << clock() << endl;
	}
}

int main(){
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	
	int t = gett();
#endif

	srand(time(NULL));
	cout << fixed << setprecision(10);

	while(read()) {
		solve();	
		
#ifdef _DEBUG
		cerr << "TIME = " << gett() - t << endl;
		t = gett();
#endif
	}
	return 0;
}

Use DP. f[i][j] keeps the number of subgraphs with i operations and a minimum cut of j. The transition may be in a knapsack-like manner. Add more functions (say another g[i][j]) if needed to make it faster.

There are more than one way to do DP, you can also read about other nice solutions here and here.

#include <cstdio>
#include <cstring>
typedef long long int64;
static const int MAXN = 53;
static const int MODULUS = 1e9 + 7;
#define _  %  MODULUS
#define __ %= MODULUS

int n, m;
// f[# of operations][mincut] -- total number of graphs
// g[# of operations][mincut] -- number of ordered pairs of two graphs
int64 f[MAXN][MAXN] = {{ 0 }}, g[MAXN][MAXN] = {{ 0 }};
int64 h[MAXN][MAXN];

inline int64 qpow(int64 base, int exp) {
    int64 ans = 1;
    for (; exp; exp >>= 1, (base *= base)__) if (exp & 1) (ans *= base)__;
    return ans;
}
int64 inv[MAXN];

int main()
{
    for (int i = 0; i < MAXN; ++i) inv[i] = qpow(i, MODULUS - 2);

    scanf("%d%d", &n, &m);

    f[0][1] = 1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i + 1; ++j) {
            // Calculate g[i][*]
            // pair(i)(j) = graph(p)(r) in series with graph(q)(s)
            // where p+q == i-1, min(r, s) == j
            for (int p = 0; p <= i - 1; ++p) {
                int q = i - 1 - p;
                for (int r = j; r <= p + 1; ++r)
                    (g[i][j] += (int64)f[p][r] * f[q][j])__;
                for (int s = j + 1; s <= q + 1; ++s)
                    (g[i][j] += (int64)f[p][j] * f[q][s])__;
            }
            // Update all f with g[i][*]
            // Iterate over the number of times pair(i)(j) is appended in parallel, let it be t
            // h is used as a temporary array
            memset(h, 0, sizeof h);
            for (int p = 0; p <= n; ++p)
                for (int q = 1; q <= p + 1; ++q) {
                    int64 comb = 1;
                    for (int t = 1; p + t * i <= n; ++t) {
                        comb = comb * (g[i][j] + t - 1)_ * inv[t]_;
                        (h[p + t * i][q + t * j] += f[p][q] * comb)__;
                    }
                }
            for (int p = 0; p <= n; ++p)
                for (int q = 1; q <= p + 1; ++q)
                    (f[p][q] += h[p][q])__;
        }
    }

    printf("%lld\n", f[n][m]);

    return 0;
}

Break the circle down into semicircles. Then there will be 1D/1D recurrences over several functions.

#include <cstdio>
typedef long long int64;
static const int MAXN = 50004;
static const int MODULUS = 998244353;
#define _  %  MODULUS
#define __ %= MODULUS

int n;
int64 g[MAXN];
int64 f0[MAXN], f1[MAXN], f2[MAXN];

int main()
{
    scanf("%d", &n);

    g[0] = 1;
    g[2] = 1;
    for (int i = 4; i <= n; i += 2) g[i] = (g[i - 4] + g[i - 2])_;

    f0[0] = 0;
    f1[0] = 1;
    f2[0] = 4;
    for (int i = 1; i <= n; ++i) {
        f0[i] = g[i] * i _ * i _;
        for (int j = 1; j <= i - 2; ++j) {
            f0[i] += g[j] * j _ * j _ * f0[i - j - 1]_;
            f0[i] += g[j - 1] * j _ * j _ * f1[i - j - 2]_;
        }
        f1[i] = g[i] * (i + 1)_ * (i + 1)_ + f0[i - 1];
        for (int j = 1; j <= i - 2; ++j) {
            f1[i] += g[j] * (j + 1)_ * (j + 1)_ * f0[i - j - 1]_;
            f1[i] += g[j - 1] * (j + 1)_ * (j + 1)_ * f1[i - j - 2]_;
        }
        f0[i]__; f1[i]__;
    }
    for (int i = 1; i <= n; ++i) {
        f2[i] = g[i] * (i + 2)_ * (i + 2)_ + f1[i - 1];
        for (int j = 1; j <= i - 1; ++j) {
            f2[i] += g[j] * (j + 1)_ * (j + 1)_ * f1[i - j - 1]_;
            f2[i] += g[j - 1] * (j + 1)_ * (j + 1)_ * f2[i - j - 2]_;
        }
        f2[i]__;
    }

    int64 ans = 0;

    ans += (g[n - 1] + g[n - 3]) * (n - 1)_ * (n - 1)_ * n _;
    for (int i = 2; i <= n - 2; ++i) {
        ans += g[i - 1] * (i - 1)_ * (i - 1)_ * f0[n - i - 1]_ * i _;
        ans += g[i - 2] * (i - 1)_ * (i - 1)_ * f1[n - i - 2]_ * 2 * i _;
        if (i >= 3 && i <= n - 3)
            ans += g[i - 3] * (i - 1)_ * (i - 1)_ * f2[n - i - 3]_ * i _;
    }

    printf("%lld\n", ans _);

    return 0;
}

#include <cstdio>
#include <cstring>
typedef long long int64;
static const int LOGN = 18;
static const int MAXN = 1 << LOGN;
static const int MODULUS = 998244353;
static const int PRIMITIVE = 2192;
#define _  %  MODULUS
#define __ %= MODULUS
template <typename T> inline void swap(T &a, T &b) { static T t; t = a; a = b; b = t; }

int n;
int64 g[MAXN];
int64 g0[MAXN], g1[MAXN], g2[MAXN];
int64 f0[MAXN], f1[MAXN], f2[MAXN];

int64 q0[MAXN], q1[MAXN];
int64 t1[MAXN], t2[MAXN], t3[MAXN], t4[MAXN];

inline int qpow(int64 base, int exp)
{
    int64 ans = 1;
    for (; exp; exp >>= 1) { if (exp & 1) (ans *= base)__; (base *= base)__; }
    return ans;
}

int bitrev[LOGN][MAXN];
int root[2][LOGN];
inline void fft(int n, int64 *a, int direction)
{
    int s = __builtin_ctz(n);
    int64 u, v, r, w;
    for (int i = 0; i < n; ++i) if (i < bitrev[s][i]) swap(a[i], a[bitrev[s][i]]);
    for (int i = 1; i <= n; i <<= 1)
        for (int j = 0; j < n; j += i) {
            r = root[direction == -1][__builtin_ctz(i)];
            w = 1;
            for (int k = j; k < j + (i >> 1); ++k) {
                u = a[k];
                v = (a[k + (i >> 1)] * w)_;
                a[k] = (u + v)_;
                a[k + (i >> 1)] = (u - v + MODULUS)_;
                w = (w * r)_;
            }
        }
}

inline void convolve(int n, int64 *a, int64 *b, int64 *c)
{
    static int64 a1[MAXN], b1[MAXN];
    memcpy(a1, a, n * 2 * sizeof(int64));
    memcpy(b1, b, n * 2 * sizeof(int64));
    memset(a + n, 0, n * sizeof(int64));
    memset(b + n, 0, n * sizeof(int64));
    fft(n * 2, a, +1);
    fft(n * 2, b, +1);
    int64 q = qpow(n * 2, MODULUS - 2);
    for (int i = 0; i < n * 2; ++i) c[i] = a[i] * b[i]_;
    fft(n * 2, c, -1);
    for (int i = 0; i < n; ++i) c[i] = c[i] * q _;
    memcpy(a, a1, n * 2 * sizeof(int64));
    memcpy(b, b1, n * 2 * sizeof(int64));
}

// Calcukates f0 and f1.
void solve_1(int l, int r)
{
    if (l == r) {
        (f0[l] += g0[l])__;
        (f1[l] += g1[l])__;
        return;
    }

    int m = (l + r) >> 1;

    solve_1(l, m);

    int len = 1;
    while (len < r - l + 1) len <<= 1;
    for (int i = 0; i < len; ++i) q0[i] = (i + l <= m ? f0[i + l] : 0);
    for (int i = 0; i < len; ++i) q1[i] = (i + l <= m ? f1[i + l] : 0);
    for (int i = len; i < len * 2; ++i) q0[i] = q1[i] = 0;
    convolve(len, g0, q0, t1);
    convolve(len, g1, q0, t2);
    convolve(len, g1, q1, t3);
    convolve(len, g2, q1, t4);

    for (int i = 0; i < len; ++i) {
        if (i + l >= m + 1 - 1 && i + l <= r - 1) {
            (f0[i + l + 1] += t1[i])__;
            (f1[i + l + 1] += t2[i])__;
        }
        if (i + l >= m + 1 - 3 && i + l <= r - 3) {
            (f0[i + l + 3] += t3[i])__;
            (f1[i + l + 3] += t4[i])__;
        }
    }

    solve_1(m + 1, r);
}

// Calculates f2.
void solve_2(int l, int r)
{
    if (l == r) {
        (f2[l] += (g2[l] + (l >= 1 ? t1[l - 1] : 0)))__;
        return;
    }

    int m = (l + r) >> 1;

    solve_2(l, m);

    int len = 1;
    while (len < r - l + 1) len <<= 1;
    for (int i = 0; i < len; ++i) q0[i] = (i + l <= m ? f2[i + l] : 0);
    for (int i = len; i < len * 2; ++i) q0[i] = 0;
    convolve(len, g2, q0, t2);

    for (int i = 0; i < len; ++i) {
        if (i + l >= m + 1 - 3 && i + l <= r - 3) {
            (f2[i + l + 3] += t2[i])__;
        }
    }

    solve_2(m + 1, r);
}

int main()
{
    for (int s = 0; s < LOGN; ++s)
        for (int i = 0; i < (1 << s); ++i)
            bitrev[s][i] = (bitrev[s][i >> 1] >> 1) | ((i & 1) << (s - 1));
    for (int i = 0; i < LOGN; ++i) {
        root[0][i] = qpow(PRIMITIVE, MAXN >> i);
        root[1][i] = qpow(PRIMITIVE, MAXN - (MAXN >> i));
    }

    scanf("%d", &n);

    g[0] = 1;
    g[2] = 1;
    for (int i = 4; i <= n; i += 2) g[i] = (g[i - 4] + g[i - 2])_;
    for (int i = 0; i <= n; ++i) {
        g0[i] = g[i] * i _ * i _;
        g1[i] = g[i] * (i + 1)_ * (i + 1)_;
        g2[i] = g[i] * (i + 2)_ * (i + 2)_;
    }

    solve_1(0, n);

    int len = 1;
    while (len < n) len <<= 1;
    convolve(len, g1, f1, t1);
    solve_2(0, n);

    int64 ans = 0;

    ans += (g[n - 1] + g[n - 3]) * (n - 1)_ * (n - 1)_ * n _;
    for (int i = 2; i <= n - 2; ++i) {
        ans += g0[i - 1] * f0[n - i - 1]_ * i _;
        ans += g1[i - 2] * f1[n - i - 2]_ * 2 * i _;
        if (i >= 3 && i <= n - 3)
            ans += g2[i - 3] * f2[n - i - 3]_ * i _;
    }

    printf("%lld\n", ans _);

    return 0;
}