[PYTHON] Yukicoder-Wettbewerb 266 Bewertung
Ergebnis
Impressionen
Ich war ungeduldig, weil ich D nicht lösen konnte, aber wenn ich darüber nachdenke, kann ich es lösen, indem ich einfach die Formel transformiere. Auch wenn ich auf die Idee des E-Problems gekommen bin, konnte ich den Rechenaufwand nicht analysieren. ** Beachten Sie, dass die Analyse mit harmonischen Reihen wichtig ist **.
In letzter Zeit wurde die Überprüfung vernachlässigt und verschiedene Dinge wurden verzögert, daher möchte ich den Rhythmus der Überprüfung anpassen.
Problem A
Versuchen Sie es bis zu $ [\ frac {n} {5}] $ mal, konvertieren Sie bis zu $ [\ frac {n} {2}] $, Strafziel bis zu $ [\ frac {n} {3} ] $ Times. Da $ N $ 100 oder weniger beträgt, können Sie auch alle durchsuchen. Beachten Sie jedoch, dass es sich um die Anzahl der Conversions $ \ leqq $ und die Anzahl der Versuche handelt.
A.py
n=int(input())
ans=0
for i in range(n//5+1):
for j in range(n//2+1):
for k in range(n//3+1):
ans+=(i*5+j*2+k*3==n and i>=j)
print(ans)
B-Problem
Erstens haben die Wahrscheinlichkeiten der Schatztruhe nichts mit der Antwort zu tun. Sagen wir also $ p \ leqq q \ leqq r $.
Markieren Sie zu diesem Zeitpunkt eine Schatzkiste und ** BLEIBEN oder ÄNDERN **. Bei Auswahl von STAY ist ** STAY to the Treasure Chest mit der höchsten Wahrscheinlichkeit das Maximum **, sodass die Wahrscheinlichkeit, einen Diamanten zu erhalten, gleich der Wahrscheinlichkeit ist, einen Diamanten in der ausgewählten Schatzkiste zu haben $ r / (p + q + r) Es ist $. Wenn Sie ÄNDERN auswählen, ** ändert sich die maximale Wahrscheinlichkeit von der Schatzkiste mit der niedrigsten Wahrscheinlichkeit **, sodass die Wahrscheinlichkeit, einen Diamanten zu erhalten, der Wahrscheinlichkeit entspricht, dass sich ein Diamant in der nicht ausgewählten Schatzkiste befindet $ (q + r) / ( p + q + r) $.
Daher lautet die Antwort $ max (r / (p + q + r), (q + r) / (p + q + r)) = (q + r) / (p + q + r) $.
B.py
p,q,r=sorted(list(map(int,input().split())))
print((q+r)/(p+q+r))
C-Problem
Erstens ist es wichtig, ein Vielfaches von 10 zu sein. Betrachten Sie also $ mod \ 10 $ für jede Karte. Wenn Sie eine Karte auswählen, ändert sich auch der Wert von $ mod \ 10 $, und ** berücksichtigen Sie den DP, den Sie mit der maximalen Anzahl von Karten haben können, die Sie auswählen können. Stellen Sie DP zu diesem Zeitpunkt wie folgt ein.
$ dp [i]: = $ (maximale Anzahl von Blättern, wenn der Rest $ i $ ist)
Außerdem wird der Übergang wie folgt aussehen, wenn die Karte $ A \ _j $ ausgewählt wird.
Außerdem ist ** der Übergang nicht einseitig **, sodass Sie ** $ dp $ kollektiv ** aktualisieren müssen, wenn Sie Karte $ A \ _j $ auswählen. Daher sollte jede Aktualisierung der Karte $ A \ _j $ in $ dp \ _sub $ gespeichert und in $ dp $ aufgezeichnet werden, nachdem die Karte $ A \ _j $ ausgewählt wurde.
C.py
ans=0
n=int(input())
check=[0 for i in range(10)]
a=list(map(int,input().split()))
for i in a:
check[i%10]+=1
dp=[0 for i in range(10)]
for i in range(10):
for j in range(check[i]):
dp_sub=[0]*10
for k in range(10):
if k==0:
dp_sub[(i+k)%10]=dp[k]+1
elif dp[k]!=0:
dp_sub[(i+k)%10]=dp[k]+1
for k in range(10):
dp[k]=max(dp[k],dp_sub[k])
#print(dp_sub)
#print(dp)
print(dp[0])
D Problem
Ich habe während und nach dem Wettbewerb eine Weile darüber nachgedacht, aber ich habe es nicht verstanden. Es könnte gelöst worden sein, wenn ich einen Kopf hätte.
Es ist schwer, sich auffällige Regeln und typische Lösungen vorzustellen, aber da es sich um ein ** Problem der Beziehung zwischen Primzahlen und Potenzen ** handelt, werde ich ** Fermats kleinen Satz ** verwenden. Der Satz von Fermat lautet wie folgt.
Wenn p eine Primzahl und a eine Primzahl mit p ist, a^{p-1} = 1\ (mod \ p) \\
Um dies zu zeigen, aus dem Binomialsatz a^{p} = a\ (mod \ p)Zeig nur.
Erstens, wenn Sie den Wert so wie er ist in Fermats Theorem einsetzen, gilt $ 2 ^ {p \ _ i-1} = 1 \ (mod \ p \ _ i) $… ①, also überlegen Sie, ** diese Formel zu transformieren ** Ich werde. Außerdem müssen ** 2 und $ p \ _i $ zueinander primieren **, dies ist jedoch nur dann der Fall, wenn $ p \ _i = 2 $ ist, was $ x = 2 $ ist. Wenn Sie hier die Kraft beider Seiten ** von ** ① nehmen, ändert sich der Wert auf der rechten Seite nicht, aber der Wert auf der linken Seite ändert sich. Mit anderen Worten, wenn Sie die $ t $ Potenzen auf beiden Seiten von ① nehmen, gilt $ 2 ^ {t (p \ _ i-1)} = 1 \ \ (mod \ p \ _i) $. Außerdem möchten Sie finden, wenn $ 2 ^ {t (p \ _ i-1)} = t (p \ _ i-1) \ \ (mod \ p \ _i) $. Wenn also ** zwei Seiten kombiniert werden **, wird $ t (p \ _ i-1) = 1 \ \ (mod \ p \ _ i) $ festgelegt. Wenn $ t = p \ _i-1 $ von $ p \ _i-t = 1 \ \ (mod \ p \ _i) $ gesetzt wird, ist dies erfüllt und $ x = (p \ _ i-1) ) ^ 2 $ ist kleiner als $ 10 ^ {18} $, also erfüllt es mit Sicherheit die fraglichen Kriterien.
Aus dem Obigen ergibt sich das Subjekt aus $ x = 2 $, wenn $ p \ _i = 2 $ und $ x = (p \ _ i-1) ^ 2 $, wenn $ p \ neq 2 $.
D.py
for i in range(int(input())):
n=int(input())
print(2 if n==2 else (n-1)**2)
E Problem
Ich habe viel gelernt, weil ** Computeranalyse nach harmonischen Reihen ** die erste Art von Problem war, die ein wichtiges Problem löste. Dieser Artikel kann als Referenz für die harmonisierte Reihe verwendet werden.
Ermitteln Sie zunächst die Summe der Werte von $ A \ _i % A \ _j $ für jedes $ i, j $. Bei einem solchen ** Gesamtproblem ist es gut, auf jeden Wert ** zu achten **, aber es ist schwierig, wenn er zu viel bleibt. Betrachten Sie also ** Paraphrase **. Mit anderen Worten, $ A \ _i % A \ _j = A \ _i - [\ frac {A \ _i} {A \ _j}] \ mal A \ _j $. Zu diesem Zeitpunkt ist $ A \ i $ $ n \ sum {i = 1} ^ {n} A \ _i $, daher kann es mit $ O (N) $ berechnet werden, aber $ [\ frac {A \ _i} {A \ _ j}] \ times A \ _ j $ ist nicht leicht zu finden.
Wenn Sie hier $ A \ _j $ reparieren, gibt es möglicherweise $ i $, das mit ** $ [\ frac {A \ _i} {A \ _j}] \ times A \ _j $ ** übereinstimmt Da dies der Fall ist, ist $ A \ _j $ festgelegt (denn wenn $ \ weil $ übereinstimmt, kann ** in den meisten Fällen zusammen berechnet werden **). Wenn die Werte übereinstimmen und $ [\ frac {A \ _i} {A \ _j}] = k $, $ A \ _j \ mal k \ leqq A \ i <A \ j \ mal (k +) 1) Da es $ sein wird, werden wir es zusammen mit dem Bild der ** Häufigkeitsverteilung ** zählen. Wenn zu diesem Zeitpunkt die Zahlenspalten $ A $ in aufsteigender Reihenfolge angeordnet sind, ist es möglich, ** mithilfe der Dichotomie herauszufinden, wie viele Zahlen einem bestimmten $ k $ entsprechen. Ebenfalls. Um die Effizienz der Berechnung zu verbessern, wird die Summe, wenn sie auf ein bestimmtes $ A \ j $ festgelegt ist, im Wörterbuch gespeichert. Wenn dieselbe Zahl angezeigt wird, wird die im Wörterbuch gespeicherte Zahl verwendet. Außerdem hat jedes $ A \ j $ ein Maximum von $ [\ frac {A \ _ {max}} {A \ _ j}] $, und jede Suche kostet $ O (\ log {n}) $. , Der Gesamtbetrag der Berechnung beträgt $ O (\ sum \ _ {j = 1} ^ {n} [\ frac {A \ _ {max}} {A \ _ j}] \ log {n}) = O (A { max} \ log {n} \ sum \ _ {j = 1} ^ {n} [\ frac {1} {A \ _ j}]) $. Auch hier aus ** Konzept der harmonischen Reihe ** (✳︎) ist $ O (\ sum \ _ {j = 1} ^ {n} [\ frac {1} {A \ _ j}]) = O (\ log Seit {A {max}}) $ beträgt der Gesamtbetrag der Berechnung $ O (A {max} \ log {n} \ log {A {max}}) $.
(✳︎)… ** Ich möchte es so machen, dass ich, wenn ich die Summenform der Brüche sehe, sie auf eine Harmonie-Reihe reduzieren kann **!
E.py
n=int(input())
a=list(map(int,input().split()))
a.sort()
from bisect import bisect_left,bisect_right
ans=0
d=dict()
for i in range(n):
if a[i] in d:
ans+=d[a[i]]
continue
ans_sub=0
j=i
while j!=n:
x=a[j]//a[i]
b=bisect_left(a,(x+1)*a[i],lo=j)-1
ans_sub+=(x*(b-j+1)*a[i])
j=b+1
d[a[i]]=ans_sub
ans+=ans_sub
print(sum(a)*n-ans)
F Problem
Ich habe den Code in [diesen Artikel] kopiert (https://algo-logic.info/segment-tree/). Wenn es sich um ein einfaches Problem handelt, können Sie eine andere Bibliothek verwenden, aber es ist ein schwieriges Problem, und Sie können nicht dasselbe tun. Daher möchte ich ** so schnell wie möglich eine Segmentbaumbibliothek erstellen **.
F.cc
//Debug-Optionen:-fsanitize=undefined,address
//Compileroptimierung
#pragma GCC optimize("Ofast")
//Einschließen usw.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//Makro
//für Schleife
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Enden)、のどちらOder
//Schleifenvariablen ohne D werden um 1 erhöht, und Schleifenvariablen mit D werden um 1 dekrementiert.
//FORA ist ein Bereich für Aussagen(Wenn es schwer zu bedienen ist, löschen Sie es)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x ist ein Container wie ein Vektor
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//Konstante
#define MOD 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays
//Abkürzung
#define PB push_back //Einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares
/* RMQ：[0,n-1]Struktur, die den Mindestwert für jeden Abschnitt verwaltet
set(i,x), build():Setzen Sie das i-te Element auf x. Erstellen Sie gemeinsam einen Seg-Baum. Ö(n)
add(a,b,x):Sektion[a,b)Fügen Sie dem Element von x hinzu. Ö(log(n))
query(a,b):Sektion[a,b)Holen Sie sich das kleinste Element in. Ö(log(n))
find_rightest(a,b,x): [a,b)Suchen Sie die Position ganz rechts mit Elementen kleiner oder gleich x. Ö(log(n))
find_leftest(a,b,x): [a,b)Suchen Sie die Position ganz links mit Elementen kleiner oder gleich x. Ö(log(n))
*/
template <typename T>
struct RMQ {
const T INF = numeric_limits<T>::max();
int n;
vector<T> dat, lazy;
RMQ(int n_) : n(), dat(n_ * 4, INF), lazy(n_ * 4, 0) {
int x = 1;
while (n_ > x) x *= 2;
n = x;
}
void set(int i, T x) { dat[i + n - 1] = x; }
void build() {
for (int k = n - 2; k >= 0; k--) dat[k] = min(dat[2 * k + 1], dat[2 * k + 2]);
}
/* lazy eval */
void eval(int k) {
if (lazy[k] == 0) return; //Beenden Sie das Programm, wenn nichts aktualisiert werden muss
if (k < n - 1) { //Wenn es kein Blatt ist, breitet es sich auf das Kind aus
lazy[k * 2 + 1] += lazy[k];
lazy[k * 2 + 2] += lazy[k];
}
//Aktualisiere dich
dat[k] += lazy[k];
lazy[k] = 0;
}
void add(int a, int b, T x, int k, int l, int r) {
eval(k);
if (a <= l && r <= b) { //Wenn ganz drinnen
lazy[k] += x;
eval(k);
} else if (a < r && l < b) { //Wenn einige Abschnitte abgedeckt sind
add(a, b, x, k * 2 + 1, l, (l + r) / 2); //Linkes Kind
add(a, b, x, k * 2 + 2, (l + r) / 2, r); //Richtiges Kind
dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
}
}
void add(int a, int b, T x) { add(a, b, x, 0, 0, n); }
T query_sub(int a, int b, int k, int l, int r) {
eval(k);
if (r <= a || b <= l) { //Wenn ganz draußen
return INF;
} else if (a <= l && r <= b) { //Wenn ganz drinnen
return dat[k];
} else { //Wenn einige Abschnitte abgedeckt sind
T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return min(vl, vr);
}
}
T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
T find_rightest(int a, int b, int x) { return find_rightest_sub(a, b, x, 0, 0, n); } //Wenn es nicht existiert a-1
T find_leftest(int a, int b, int x) { return find_leftest_sub(a, b, x, 0, 0, n); } //Wenn es nicht existiert b
T find_rightest_sub(int a, int b, int x, int k, int l, int r) {
eval(k);
if (dat[k] > x || r <= a || b <= l) { //Ihr Wert ist größer als x oder[a,b)Aber[l,r)Wenn es außerhalb des Bereichs von liegt, geben Sie a zurück-1
return a - 1;
} else if (k >= n - 1) { //Wenn Sie ein Blatt sind, geben Sie diese Position zurück
return (k - (n - 1));
} else {
int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
if (vr != a - 1) { //Schauen Sie sich den Teilbaum rechts an. A.-Wenn nicht 1, kehren Sie zurück
return vr;
} else { //Schauen Sie sich den Teilbaum links an und geben Sie den Wert zurück
return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
}
}
}
T find_leftest_sub(int a, int b, int x, int k, int l, int r) {
eval(k);
if (dat[k] > x || r <= a || b <= l) { //Ihr Wert ist größer als x oder[a,b)Aber[l,r)Wenn es außerhalb des Bereichs von liegt, geben Sie b zurück
return b;
} else if (k >= n - 1) { //Wenn Sie ein Blatt sind, geben Sie diese Position zurück
return (k - (n - 1));
} else {
int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
if (vl != b) { //Schauen Sie sich den Teilbaum links an und kehren Sie zurück, wenn es sich nicht um b handelt
return vl;
} else { //Schauen Sie sich den Teilbaum rechts an und geben Sie den Wert zurück
return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
}
}
}
/* debug */
inline T operator[](inta){returnquery(a,a+1); }
void print() {
for (int i = 0; i < n; ++i) {
cout << (*this)[i];
if (i != n) cout << ",";
}
cout << endl;
}
};
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n;
RMQ<ll> x(n);
REP(i,n){
ll y;cin>>y;
x.set(i,y);
}
x.build();
ll q;cin>>q;
REP(i,q){
ll k,l,r,c;cin>>k>>l>>r>>c;
if(k==1){
x.add(l-1,r,c);
}else{
cout<<x.query(l-1,r)<<endl;
}
}
//x.print();
}
Recommended Posts